企业官网建设流程全解析

上周刷 LeetCode 的时候，卡在 879 这道「盈利计划」上整整两天。题目标签是 Hard，但读完之后你会发现它并不是那种思维极度跳跃的题，而是一道非常标准的二维费用背包。真正难住我的地方是状态定义：题目说的是「利润至少为 minProfit」，这个「至少」二字，决定了整套 DP 方程长什么样。我第一次写的时候直接用「恰好利润」的思路，结果要么数组越界，要么答案差一位，折腾了很久才把问题看透。这篇文章就把我从读题、设计状态、写转移方程到最终 AC 的完整过程，连同踩过的坑一起记录下来，给正在刷动态规划或者面试前想快速过一遍背包变形的 Java 同学做个参考。

1. LeetCode 879 盈利计划到底在考什么

1.1 题目还原：输入是什么，输出是什么

先把题目用最直白的话翻译一遍。公司里有 n 名员工，现在有 m 种工作任务，第 i 种任务需要 group[i] 个人参与，完成后会产生 profit[i] 的利润。每个任务最多只能执行一次，要求参与工作的员工总数不超过 n，并且总利润至少要达到 minProfit，问一共有多少种选任务的方案。因为结果可能非常大，题目要求对 1_000_000_007 取模后返回。

读题时有两点特别容易忽略。第一是「每个任务最多执行一次」，这句话直接决定了它是 0-1 背包而不是完全背包，后面循环顺序就得是逆序。第二就是「总利润至少达到 minProfit」里的「至少」，这个语义是整个题解的核心，比代码本身难得多。我第一眼看到这道题，还以为是某种收益最大化的贪心，试了两下才发现完全不是那回事。

拿示例来说。假设 n = 5，minProfit = 3，group = [2, 2]，profit = [2, 3]，那么有两个任务：任务 A 需要 2 人赚 2 利润，任务 B 需要 2 人赚 3 利润。手工枚举一下：只做 B，2 人 3 利润，满足；A 和 B 都做，4 人 5 利润，满足；只做 A，2 人 2 利润，不够；什么都不做，0 利润，不够。所以答案是 2。如果把 minProfit 改成 0，那么空方案也算一种，答案会变成 4，因为四种组合（空、A、B、A+B）的人数都不超过 5，利润也都至少为 0。这个例子对理解「至少型」状态非常有帮助。

另一个示例是 n = 10，minProfit = 5，group = [2, 3, 5]，profit = [6, 7, 8]，答案是 7。三个任务任意组合，单个选、两两组合、三个全选，一共 1 + 3 + 3 + 1 = 8 种组合，去掉空方案就是 7 种，因为每个非空组合的利润都超过 5，人数也都够。这个例子适合用来验证你的 DP 写完之后，跑出来是不是真的 7。

1.2 为什么这是一道二维费用背包而不是普通 0-1 背包

普通的 0-1 背包，状态一般是 dp[i][j]，表示前 i 个物品在容量为 j 的条件下能获得的最大价值，只有一个约束维度，就是背包容量。而这道题有两个约束：员工人数有上限 n，利润有下限 minProfit。你要同时统计「人数不超过 n」和「利润不低于 minProfit」，所以状态里必须有两个维度：一个记录人数，一个记录利润情况。

你可以这么理解：食堂打饭，你手里