1. 题目理解与核心思路拆解1.1 先把这个题意翻译成人话LeetCode 879这道题我最早是在一次模拟面试里遇到的。当时看完题目第一反应是这不就是个背包吗但真下手写的时候发现被“至少盈利”这四个字卡了好一会儿。先把题目参数列一下。方法签名是public int profitableSchemes(int n, int minProfit, int[] group, int[] profit)四个入参的意思分别是n公司总共有多少名员工最多能派出去的人数。minProfit要求至少达到的利润目标。group数组group[i]表示完成第i个犯罪计划至少需要多少人。profit数组profit[i]表示完成第i个犯罪计划能获得的利润。题目要求的是从这些计划中选出一个集合满足两个条件——用到的总人数不超过n产生的总利润不低于minProfit。求一共有多少种选法结果对10^9 7取模。为什么这道题在 LeetCode 上被标成 Hard不是因为状态转移有多复杂而是很多人被“利润不低于 minProfit”这个约束绕进去了。常规背包问题都是“不超过容量”的约束比如“总重量不超过 W”这里多了一个下限约束“总利润至少为 P”。一上一下处理方式完全不同。1.2 为什么说它是二维费用背包背包问题的本质是有一堆物品每个物品有费用、有价值在费用受限的情况下让价值最大化或者统计方案数。这道题里每个计划就是一个物品它有两个维度的费用人数group[i]和利润profit[i]。如果只考虑人数上限n那就是个普通的一维 0/1 背包物品计划选或不选统计方案数。但现在还需要考虑利润目标minProfit所以状态里必须额外记录当前累计利润的信息。于是状态就从一维变成了二维。有人会问人数是费用利润也是费用吗严格来说在这道题里可以把利润看成第二个容量维度。不过它和普通容量有个关键区别普通容量的限制是“不能超过”利润的限制是“不能低于”。这个区别决定了后面状态设计时的具体处理方式。还有一个容易被忽视的点每个计划只能选一次这是典型的0/1 背包不是完全背包。所以后面做空间优化的时候循环方向必须注意不能写成完全背包那样正序遍历。1.3 “至少盈利 minProfit”才是这道题的灵魂很多题解把利润维度直接定为minProfit 1的大小下标从 0 到minProfit然后转移的时候用到一个关键操作newProfit Math.min(minProfit, currentProfit profit[i])这个Math.min是什么意思它的作用是把超过 minProfit 的利润全部“截断”到 minProfit 这一档。举个具体的例子。假设minProfit 5某个方案能带来利润 10。那么在状态转移时我们不区分“利润是 6”和“利润是 10”这两种情况统一都算作“利润达到 5”。因为题目只要求“至少 5”利润 6 和利润 10 在判断是否满足条件这件事上完全等价。这个思路非常关键。如果你不用这个截断把利润维度开到所有计划利润之和的大小那状态数组会变得巨大无比。比如minProfit只有 10但profit数组求和后有 1000你为了记录所有可能的利润就得开一个长度为 1001 的维度。而实际上超过 10 的部分对答案没有任何贡献纯属浪费。所以这道题本质上就是一个二维费用 0/1 背包其中一维费用人数取上界另一维利润取下界然后通过封顶技巧把下界约束转化成上界约束来处理。2. 三维DP状态定义与转移逻辑2.1 状态定义dp[i][j][k] 到底表示什么在讲优化版之前先把最朴素的三维 DP 捋清楚。写动态规划的第一步永远是明确状态这一步错了后面全白搭。定义dp[i][j][k] 表示从前 i 个计划中选恰好用了 j 个人获得的利润为 k超过 minProfit 的部分截断到 minProfit时的方案数。这里有几个细节要说明。第一i的范围是0到mm group.length表示考虑了前几个计划。dp[0][j][k]表示一个计划都不考虑的情况。第二j的范围是0到n表示人数。这里取的是“恰好用了 j 个人”的语义。后面会说这个“恰好”和“不超过”的区别对最终答案统计的影响。第三k的范围是0到minProfit表示利润。但这里的利润是截断后的利润不是真实利润。比如minProfit 5一个计划赚了 100状态里的k记录的是 5 而不是 100。第四为什么利润维度只需要minProfit 1因为任何超过minProfit的利润状态在判断是否满足条件时都等价于minProfit。截断的目的是压缩状态空间同时不丢失判断条件所需的信息。2.2 状态转移选与不选的经典套路三维 DP 的转移逻辑和普通 0/1 背包一脉相承对于第i个计划只有两种选择——不选它或者选它。不选第i个计划dp[i][j][k] dp[i - 1][j][k]意思是前i - 1个计划已经能达到状态(j, k)第i个计划不参与那么方案数直接继承。选第i个计划前提是j group[i]否则人不够选不了。newProfit Math.min(minProfit, k profit[i]) dp[i][j][newProfit] dp[i - 1][j - group[i]][k]这里dp[i - 1][j - group[i]][k]表示在前i - 1个计划中恰好用了j - group[i]个人、利润为k的方案数。在此基础上选第i个计划人数变成j - group[i] group[i] j利润从k增加profit[i]截断后变成newProfit。有人可能会问为什么累加的目标是dp[i][j][newProfit]而不是dp[i][j][k profit[i]]原因就是前面强调的截断。如果k profit[i]超过minProfit我们统一记到minProfit这一档。2.3 初始化与答案统计两个容易出错的细节初始化的逻辑很简单一个计划都不选用了 0 个人利润为 0这算一种方案。所以dp[0][0][0] 1其他所有dp[0][j][k]都是 0。这里有一个重要的细节dp[0][0][0] 1这个初始化隐含的语义是“恰好用了 0 个人恰好利润为 0”。如果题目要求的是“不超过 n 个人”那么最后统计答案时不能只输出dp[m][n][minProfit]因为可能有人数没派满的情况。正确做法是把所有人数档位的方案数加起来ans sum(dp[m][j][minProfit]) for j 0..n有人可能觉得奇怪为什么只看k minProfit这一档因为截断后所有利润不低于minProfit的方案都归入了这一档。所以只要看k minProfit的格子就等价于所有满足“利润至少为 minProfit”的方案数。还有一个隐形细节ans要不要算上空的选法如果minProfit 0一个计划都不选利润为 0也是合法的方案吗从题目语义来看选空集意味着没做任何计划利润恰好为 0满足“至少 0”的条件。所以在minProfit 0时空集也算一个方案。三维 DP 的初始化dp[0][0][0] 1会自动把这个空集方案计入不需要额外处理。3. 空间优化降维到二维 dp[j][k]3.1 从三维到二维滚动数组的思路三维 DP 的数组大小是m * (n 1) * (minProfit 1)。题目数据范围里m最多100n最多100minProfit最多100所以100 * 101 * 101大概 100 万其实也能开。但 LeetCode 上这道题的标准解法基本都会用二维数组一方面是更优雅另一方面也让代码更接近面试时手写的要求。为什么能降维观察转移方程可以发现dp[i]这一层只依赖dp[i - 1]这一层跟dp[i - 2]、dp[i - 3]都没有关系。这就是典型的滚动数组优化——只需要保留上一层的状态就能推出当前层。更彻底的做法是把i这一维直接去掉用二维数组dp[j][k]原地更新。但这里有个前提更新的方向必须保证dp[j - g][k]读到的是“上一轮”的旧值而不是这一轮已经被新计划更新过的新值。这就引出了 0/1 背包中经典的反向遍历问题。3.2 组员数维度为什么要逆序遍历为了说清楚这个问题先看未优化时的转移dp[i][j][newProfit] dp[i - 1][j - group[i]][k]降维后变成dp[j][newProfit] dp[j - group[i]][k]在二维循环里如果我们正序遍历j假设group[i] 1当j 1时更新了dp[1][...]接着j 2时要用dp[1][...]读到的就是已经被当前计划更新过的新值。这等于说第i个计划被重复使用了两次、三次……完全违背了 0/1 背包“每个物品只能选一次”的约束。解决办法就是逆序遍历j从n往group[i]方向遍历。因为j - group[i] j逆序遍历时dp[j - group[i]][...]一定还没被这一轮更新读到的必然是上一轮的旧值。这里我要多说一句很多初学者背口诀“0/1 背包逆序完全背包正序”但不知道背后的原因。你现在看到的这段解释就是那个口诀的来由。理解了这个面试时被问“为什么逆序”就不会卡壳。3.3 利润维度 k 的遍历方向关于k维度的遍历方向不同题解写得不一样有的正序有的逆序。我在确认正确性时仔细推演过k的方向对结果没有影响因为利润维度的转移目标newProfit是min(minProfit, k profit[i])它总是大于等于k当profit[i] 0时相等。但为什么有的题解写成逆序主要是为了代码风格统一让人一看就觉得“这是 0/1 背包”。我自己写的时候也习惯逆序因为这样不需要额外解释“为什么这个维度可以正序”减少读者心智负担。不过要强调的是j维必须逆序这是硬性要求k维正序逆序都可但如果profit[i]可能为 0从代码自解释角度推荐统一逆序。4. Java代码实现与逐段讲解4.1 完整可提交的代码先给完整代码再逐段拆开讲class Solution { public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { int m group.length; int MOD 1_000_000_007; // dp[j][k]: 恰好用 j 个人利润为 k截断到 minProfit的方案数 int[][] dp new int[n 1][minProfit 1]; dp[0][0] 1; for (int i 0; i m; i) { int g group[i]; int p profit[i]; for (int j n; j g; j--) { for (int k minProfit; k 0; k--) { int newProfit Math.min(minProfit, k p); dp[j][newProfit] (dp[j][newProfit] dp[j - g][k]) % MOD; } } } int ans 0; for (int j 0; j n; j) { ans (ans dp[j][minProfit]) % MOD; } return ans; } }4.2 核心代码段逐行分析初始化部分int[][] dp new int[n 1][minProfit 1]; dp[0][0] 1;这里把dp[0][0]设为 1代表“什么都不选”这一种方案。n 1是因为人数从 0 到n共n 1个取值minProfit 1同理。如果minProfit 0第二维长度就是 1代码依然成立。外层枚举计划for (int i 0; i m; i) { int g group[i]; int p profit[i];没啥好说的就是遍历所有计划。取出group[i]和profit[i]存到局部变量一方面是代码清爽另一方面避免在深层循环里反复访问数组元素虽然这点性能差异微乎其微但写习惯了并不亏。人数维逆序枚举for (int j n; j g; j--) {这个循环从n递减到g因为如果j g人数不够选这个计划直接跳过。逆序的原因是防止重复选择当前计划前面已经详细解释过不再赘述。利润维枚举for (int k minProfit; k 0; k--) { int newProfit Math.min(minProfit, k p); dp[j][newProfit] (dp[j][newProfit] dp[j - g][k]) % MOD; }这里逐维拆解一下k遍历当前累计利润截断后的。newProfit表示加入当前计划后的新利润如果超过minProfit就截断到minProfit。dp[j - g][k]是上一轮“没选当前计划、人数少了 g 个、利润为 k”的方案数。累加到dp[j][newProfit]表示选当前计划后到达的新状态。每次加法后立刻取模防止溢出。答案统计int ans 0; for (int j 0; j n; j) { ans (ans dp[j][minProfit]) % MOD; }因为状态定义是“恰好用 j 个人”而题目只要求“不超过 n 个人”所以把j 0到n的所有满足利润条件的方案数累加。这一步千万别漏漏掉的话测试用例很可能挂掉。4.3 复杂度分析时间复杂度O(m * n * minProfit)。三重循环每个维度相乘。因为m、n、minProfit上限都是 100所以最多100 * 100 * 100 1,000,000次操作完全在可接受范围内。空间复杂度O(n * minProfit)。二维数组100 * 100 10000个格子非常小。如果面试的时候能主动说出这个复杂度并且解释为什么可以这样优化会比单纯背代码好很多。5. 边界条件与避坑指南5.1 当 minProfit 0 时答案对得上吗这是个很好的自测用例。简单推一下如果minProfit 0意味着只要利润不为负数任何选法都满足条件所有利润都非负的话任何非空子集都满足。再加上空集总共应该是2^m个方案等等这里空集算不算题目里没明说非法但dp[0][0] 1的初始化把空集方案计入所以答案应该是2^m对MOD取模。但注意如果所有profit[i]都大于 0那么空集利润是 0满足“至少 0”如果所有profit[i]都等于 0空集也满足。总之在minProfit 0时每个计划可选可不选答案是所有子集数量2^m。用代码验证当minProfit 0dp[j][0]最后会被填上所有组合数累加所有j后就是2^m。如果测试时发现差了一个 1多半是初始化dp[0][0]忘写了。5.2 当 group[i] 大于 n 时会出现数组越界吗不会。因为内层 j 循环从n开始到j g结束。如果g n循环条件一开始就不成立整体跳过。所以这个计划永远选不进去天然被忽略。这个行为是符合题意的公司只有n个人一个需要n 1人的计划根本无法执行自然不能算进方案里。5.3 取模的时机int 溢出隐患MOD 1_000_000_007dp数组中的值每次累加后都会取模所以每个格子里的值一定小于MOD。两个小于MOD的数相加小于2 * MOD依然在int范围内2,000,000,014 2,147,483,647所以这里用int不会溢出。但要注意如果某个格子被多次累加且没有及时取模那确实可能爆炸。所以每次加法都要立刻取模不要想着“最后答案再取模一次”。我在实际编码中见过有人把取模放到全部循环结束之后数据一大就 WA答案错误原因就是中间过程溢出。5.4 面试中的一个小陷阱方案数可能要加 long虽然这道题用int足够但有些变体题目的MOD更大或者状态值本身可能超过2^31 - 1。如果面试官追问“如果值更大怎么办”你可以说把dp数组改成long累加时先转long再取模或者直接用long存储最后强转int。6. 常见问题与排查心得实录6.1 为什么有的题解把人数维度也开成“不超过”语义我见过很多题解用dp[j][k]表示“最多用 j 个人、利润至少 k”的方案数。这种写法下的初始化通常是for (int j 0; j n; j) { dp[j][0] 1; }这里的语义内涵是最多用j个人、利润至少 0 的方案数至少为 1空集所以把这些格子都初始化成 1。然后在转移时逻辑不变但最后答案直接输出dp[n][minProfit]不用再累加人数维。两种写法都是对的但我个人更推荐“恰好用 j 个人”的版本因为它更接近 0/1 背包的原始模型而且初始化更简单不容易遗漏。面试时如果你写“恰好”语义记得在最后解释为什么要sum(dp[j][minProfit])这反而是展示你理解到位的加分点。6.2 我调试这道题时踩过的坑第一次提交时我挂在了一个很隐蔽的地方k循环写成正序然后newProfit等于k的情况没有意识到会导致同一轮内多次累加。虽然前面说过k方向本身不影响正确性但前提是人的遍历j一定是逆序。当时我犯的错误是把j也写成了正序结果答案变成了指数级的错误值。排查这个问题有个笨但有效的方法手工模拟小数据。我拿n1, minProfit1, group[1], profit[1]这样的最小用例在纸上把二维数组每个格子更新前后写一遍立刻就能发现问题在哪里。6.3 一个便宜的验证方式暴力递归对拍LeetCode 题目在写 DP 之前可以先写一个暴力枚举所有子集的版本用来对拍。比如int ans 0; for (int mask 0; mask (1 m); mask) { int people 0, profitSum 0; for (int i 0; i m; i) { if ((mask (1 i)) ! 0) { people group[i]; profitSum profit[i]; } } if (people n profitSum minProfit) { ans; } }m很小的时候比如 10 以内暴力枚举完全可行。写完之后随机生成几组小数据和 DP 版本跑同样的输入看结果是否一致。这套“暴力对拍法”在刷题时非常好用尤其适合验证状态转移方程有没有写错。我几乎每次做 DP 题都会先写暴力版本虽然不提交但能极大提升一次性 AC 的概率。6.4 这类题目在面试中的考察重点LeetCode 879 在面试里被问到的概率不高但它的变体思路很常见。面试官真正想考察的能力是能不能识别出这是一个二维费用的 0/1 背包问题能不能处理“至少”这个反向约束能不能解释清楚为什么人数维要逆序遍历能不能正确处理最终答案的统计范围。如果你能在白板上边说边写出这个代码并把上面几个问题答清楚那这道题的目的就达到了。最后再分享一个体会我当时第一次做这道题时其实没能在 20 分钟内独立 AC栽在了最终答案忘了累加多个j上。后来隔了几天重新做了一遍把状态语义彻底想清楚之后发现这类“至少型”背包问题会做了之后遇到 LeetCode 494 目标和、LeetCode 518 零钱兑换 II 这些变体上手都快了很多。刷题嘛最重要的不是记住某道题的解法而是通过一道题吃透一类题。这道盈利计划就是一个把“二维费用背包”和“反向约束处理”结合起来的最佳教材。
