LeetCode 2305中等动态规划
公平分发饼干 图解题解
这道题到底在问什么
cookies[i] 是第 i 包里的饼干数，一共要把所有包分给 k 个孩子，每包整包给一人。某种分法的「不公平程度」= 分到饼干最多的那个孩子的总数。返回所有分法里最小的不公平程度。
- 输入
- cookies=[8,15,10,20,8], k=2
- 输出
- 31 （[20,10] 给一人得 30，[15,8,8] 给另一人得 31，最大 31 最小）
- 输入
- cookies=[6,1,3,2,2,4,1,2], k=3
- 输出
- 7 （三人各拿到 7、7、7，最大 7）
最优解：一步一步想明白
- 3记住这套「逐包试着发、发完更新答案、超标就剪、重复空桶就剪」，下面每一帧都在套它。
- 4开局：孩子1、孩子2 手里都是 0 块饼干。右边是四包饼干，已经从大到小排成 6、4、3、1。我们要把每一包整包发出去，让最后拿得最多的孩子尽量少。
- 5把这包 6 发给 孩子1，它从 0 变成 6，接着发下一包。
- 6把这包 4 发给 孩子1，它从 6 变成 10，接着发下一包。
- 7把这包 3 发给 孩子1，它从 10 变成 13，接着发下一包。
- 8把这包 1 发给 孩子1，它从 13 变成 14，接着发下一包。
- 9四包都发完了，孩子1有 14、孩子2有 0，这条分法里最多的是 14。比之前记的最优还小，答案刷新成 14。
- 10换一种：把这包 1 改发给 孩子2，它从 0 变成 1，还没到已知最优 14，可以往下走。
- 11四包都发完了，孩子1有 13、孩子2有 1，这条分法里最多的是 13。比之前记的最优还小，答案刷新成 13。
- 12换一种：把这包 3 改发给 孩子2，它从 0 变成 3，还没到已知最优 13，可以往下走。
- 13把这包 1 发给 孩子1，它从 10 变成 11，还没到已知最优 13，可以往下走。
- 14四包都发完了，孩子1有 11、孩子2有 3，这条分法里最多的是 11。比之前记的最优还小，答案刷新成 11。
- 15换一种：把这包 1 改发给 孩子2，它从 3 变成 4，还没到已知最优 11，可以往下走。
- 16四包都发完了，孩子1有 10、孩子2有 4，这条分法里最多的是 10。比之前记的最优还小，答案刷新成 10。
- 17换一种：把这包 4 改发给 孩子2，它从 0 变成 4，还没到已知最优 10，可以往下走。
- 18把这包 3 发给 孩子1，它从 6 变成 9，还没到已知最优 10，可以往下走。
- 19想把这包 1 发给 孩子1，可它现在有 9，加上去是 10，已经不小于已知最优 10，这条路不可能更好，孩子1 标红剪掉。
- 20换一种：把这包 1 改发给 孩子2，它从 4 变成 5，还没到已知最优 10，可以往下走。
- 21四包都发完了，孩子1有 9、孩子2有 5，这条分法里最多的是 9。比之前记的最优还小，答案刷新成 9。
- 22换一种：把这包 3 改发给 孩子2，它从 4 变成 7，还没到已知最优 9，可以往下走。
- 23把这包 1 发给 孩子1，它从 6 变成 7，还没到已知最优 9，可以往下走。
- 24四包都发完了，孩子1有 7、孩子2有 7，这条分法里最多的是 7。比之前记的最优还小，答案刷新成 7。
- 25想把这包 1 发给 孩子2，可它现在有 7，加上去是 8，已经不小于已知最优 7，这条路不可能更好，孩子2 标红剪掉。
- 26孩子2 现在手里 0，和 孩子1 一模一样。这包发给谁效果完全相同，只留前一个就够，孩子2 这条重复分支剪掉。
- 27孩子1 起手的所有发法都试过，孩子2 起手因为和孩子1 完全对称被整支剪掉，回溯把每种本质不同的分法都走遍。最好的一种是 [6,1] 给一人、[4,3] 给另一人，最多 7，答案就是 7。
⚠️ 容易写错的地方
✗ 错：用贪心：每包发给当前最少的孩子
✓ 对：必须回溯枚举所有发法
贪心会被反例卡住，局部最少不代表最后的最大值最小
✗ 错：漏掉「当前和 ≥ 已知最优就剪」
✓ 对：加上这包 ≥ ans 立刻跳过
不剪就退化成把所有分配全枚举，n 稍大就超时
✗ 错：漏掉「与前一个孩子当前总数相同就剪」
✓ 对：cnt[j] 等于 cnt[j-1] 时跳过
两个空档发给谁完全等价，不剪会把同一种分法重复搜 k 次
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def distributeCookies(self, cookies: List[int], k: int) -> int:
def dfs(i):
if i >= len(cookies):
nonlocal ans
ans = max(cnt)
return
for j in range(k):
if cnt[j] + cookies[i] >= ans or (j and cnt[j] == cnt[j - 1]):
continue
cnt[j] += cookies[i]
dfs(i + 1)
cnt[j] -= cookies[i]
ans = inf
cnt = [0] * k
cookies.sort(reverse=True)
dfs(0)
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int distributeCookies(vector<int>& cookies, int k) {
sort(cookies.rbegin(), cookies.rend());
int cnt[k];
memset(cnt, 0, sizeof cnt);
int n = cookies.size();
int ans = 1 << 30;
function<void(int)> dfs = [&](int i) {
if (i >= n) {
ans = *max_element(cnt, cnt + k);
return;
}
for (int j = 0; j < k; ++j) {
if (cnt[j] + cookies[i] >= ans || (j && cnt[j] == cnt[j - 1])) {
continue;
}
cnt[j] += cookies[i];
dfs(i + 1);
cnt[j] -= cookies[i];
}
};
dfs(0);
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private int[] cookies;
private int[] cnt;
private int k;
private int n;
private int ans = 1 << 30;
public int distributeCookies(int[] cookies, int k) {
n = cookies.length;
cnt = new int[k];
// 升序排列
Arrays.sort(cookies);
this.cookies = cookies;
this.k = k;
// 这里搜索顺序是 n-1, n-2,...0
dfs(n - 1);
return ans;
}
private void dfs(int i) {
if (i < 0) {
// ans = Arrays.stream(cnt).max().getAsInt();
ans = 0;
for (int v : cnt) {
ans = Math.max(ans, v);
}
return;
}
for (int j = 0; j < k; ++j) {
if (cnt[j] + cookies[i] >= ans || (j > 0 && cnt[j] == cnt[j - 1])) {
continue;
}
cnt[j] += cookies[i];
dfs(i - 1);
cnt[j] -= cookies[i];
}
}
}复杂度
时间
O(k^n)
n 包每包试 k 个孩子，是搜索树上界；两把剪刀后实际远少于此
空间
O(n + k)
递归深度 O(n) 加上 k 个孩子的计数数组 O(k)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 公平分发饼干 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
除了回溯，这题还有别的解法吗？+
有状压动态规划。先预处理每个包的子集 mask 对应的饼干总和 sum[mask]，再用 dp[i][mask] 表示前 i 个孩子分掉 mask 这批包时的最小不公平程度，转移枚举 mask 的子集分给第 i 个孩子。复杂度是 O(k 乘以 3 的 n 次方)。n 最大只有 8，回溯和状压都能轻松过。
能不能二分答案加可行性判定？+
思路是二分不公平程度上限 limit，再判定「能不能把包分成 k 组、每组和都不超过 limit」。问题是这个判定本身就是装箱可行性，还是要搜索，二分外壳并没有省掉搜索的力气。n 这么小，直接回溯反而更干脆。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 公平分发饼干 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。