LeetCode 879. 盈利计划

2021-08-13 HGNULB 约 11 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 879. 盈利计划

题意分析

有 n 名员工和若干个项目，第 i 个项目需要 group[i] 名员工参与、能产生 profit[i] 的利润。每名员工最多只能参与一个项目，因此被选中的项目所需人数之和不能超过 n。要求统计有多少种项目子集，其总利润至少是 minProfit。答案对 $10^9 + 7$ 取模。

题面里有三条信号。第一，每个项目「选或不选」，且选了就要整份消耗人力——这是标准的0-1 选择结构，不是可重复取的完全背包。第二，约束有两个维度：人数是「不能超过」的上限型约束，利润是「不能低于」的下限型约束，两者方向相反，必须分别用一维状态承载。第三，问的是方案数而不是最大利润，所以转移是累加而不是取最值，初始状态也要设成「空集算一种方案」。

最值得注意的是利润这一维的处理方式。总利润理论上可以达到 $\sum profit[i]$，在极端情况下是 $100 \times 100 = 10^4$，如果按真实利润开状态会让状态数膨胀；但题目只关心「是否达到 minProfit」，超过之后再多也没有区别。这就允许把利润维度封顶在 minProfit——所有利润 $\ge minProfit$ 的情形合并成同一个状态。minProfit \le 100 这个约束正是在暗示这一点。

规模方面：$1 \le n \le 100$，$0 \le minProfit \le 100$，项目数 $g \le 100$，且每个 group[i] \ge 1。三者相乘约 $10^6$，说明 $O(g \cdot n \cdot minProfit)$ 的三重循环是预期解。

边界上要覆盖：minProfit = 0（空集也算合法方案，答案包含「一个项目都不选」）；某个项目的 profit[i] = 0（选它只消耗人力不产生利润）；所有项目人数之和小于 n（人力充裕，答案是所有利润达标的子集数）；单个项目就能超过 minProfit（封顶逻辑立刻生效）。

解法：二维 DP

核心思路

暴力做法是枚举所有项目子集，共 $2^g$ 种，$g$ 可达 $100$，完全不可能。瓶颈在于它把「选了哪些项目」当成了需要区分的信息，而实际上后续决策只依赖两个汇总量：已用掉多少人和已积累多少利润。这就是把指数级搜索压成多项式 DP 的切入点。

于是状态定义为：dp[k][j] 表示在只考虑已处理过的那些项目时，恰好使用 j 名员工、且累计利润「封顶后」等于 k 的方案数。这里「封顶」的准确含义是：真实利润若小于 minProfit 则 k 就是真实利润；真实利润若达到或超过 minProfit 则一律记作 k = minProfit。这条定义是整道题的核心，它把无界的利润维度压缩到了 $[0, minProfit]$ 这 $minProfit + 1$ 个取值上。

初始化 dp[0][0] = 1，含义是「一个项目都不选，用 $0$ 人、得 $0$ 利润」这一种方案。这个 $1$ 是所有计数的种子，漏掉它整张表全为 $0$。

转移就是 0-1 背包的标准形式。对每个项目 $(g, p)$，若选它，则由「用 j - g 人、利润 k」的方案转移到「用 j 人、利润 $\min(minProfit, k + p)$」的方案：

dp[min(minProfit, k + p)][j] += dp[k][j - g]

取 $\min$ 就是封顶的落地：一旦累加后越过 minProfit，全部归并到 minProfit 这一格。不封顶的话状态要开到 $10^4$ 那么大，而且「利润 $\ge minProfit$」的答案要在末尾遍历一大段区间去求和，既慢又容易漏。

于是要维护的不变量是：每处理完一个项目后，dp[k][j] 恒等于「在前若干个项目中做 0-1 选择，用 j 人、封顶利润为 k 的方案总数」。为了让「每个项目只被选一次」这条不变量成立，人数维度 j 必须逆序遍历（从 n 递减到 g）——顺序遍历时 dp[k][j - g] 可能已经在本轮被更新过，等价于同一个项目被选了多次，那就变成完全背包了。

利润维度 k 也写成逆序，但原因与人数维度不同。事实上由于读的是列 j - g、写的是列 j，而 g \ge 1 保证两列不同，同一轮内读写不会冲突，因此 k 的方向在本题其实是自由的；写成逆序只是与人数维度保持一致的书写习惯。值得注意的是，如果题目允许 group[i] = 0，读写就会落在同一列上，那时 k 的方向就变得关键了——本题的约束 group[i] >= 1 恰好排除了这个隐患。

最后答案是把所有人数取值下的达标状态加起来：$\sum_{j=0}^{n} dp[minProfit][j]$。之所以要对 j 求和，是因为状态里的 j 是「恰好用 j 人」，而题目只要求「不超过 n 人」，所以每一种人数都算合法；而利润维只取 minProfit 这一格，因为封顶后它已经代表了「利润达标」的全部情形。

解题步骤

开一个 (minProfit + 1) × (n + 1) 的二维数组 dp，令 dp[0][0] = 1。理由：两个维度分别对应封顶利润和已用人数；dp[0][0] = 1 是空集这一种基础方案，是所有计数的起点，缺了它答案恒为 $0$。

最外层遍历所有项目 i，取出 g = group[i]、p = profit[i]。理由：0-1 背包的物品维必须在最外层，这样「每个项目只有一次被选的机会」才有意义；把它放到内层会让同一个项目在不同人数下被反复决策。

第二层 for (int j = n; j >= g; j--) 逆序遍历人数。理由：逆序保证读取的 dp[k][j - g] 仍是上一个项目处理完毕时的值，从而每个项目至多被选一次；正序会读到本轮已更新的值，退化成可重复选取的完全背包。下界写 j >= g 是因为人数不足 g 时根本选不了这个项目，无需转移。

第三层 for (int k = minProfit; k >= 0; k--) 遍历封顶利润。理由：这一维要覆盖全部取值，因为任何已有的利润状态都可能因为选了当前项目而向上跳；写成逆序是与上一层保持一致的习惯，本题中读写分属不同列，方向不影响正确性。

计算 nk = Math.min(minProfit, k + p)，执行 dp[nk][j] = (dp[nk][j] + dp[k][j - g]) % MOD。理由：min 实现利润封顶，把所有「已达标」的情形归并到同一格；用 += 而非赋值，因为多个不同的 k 可能映射到同一个 nk（凡是 $k + p \ge minProfit$ 的都归到 minProfit），必须累加；每步取模防止 int 溢出。

全部项目处理完后，把 dp[minProfit][j] 对 j 从 $0$ 到 n 求和并取模。理由：状态定义是「恰好用 j 人」，而题目只限制人数上限，所以每个 j 都要计入；利润维只取封顶格，因为它已经代表了所有达标情形。

以 n = 5、minProfit = 3、group = [2, 2]、profit = [2, 3] 走一遍。初始 dp[0][0] = 1。处理第一个项目 $(g=2, p=2)$：j 从 $5$ 递减到 $2$，只有 j = 2 时 dp[k][0] 非零（即 k = 0 处的 $1$），此时 nk = min(3, 0 + 2) = 2，于是 dp[2][2] = 1。处理第二个项目 $(g=2, p=3)$：j 从 $5$ 递减。j = 4 时读 dp[k][2]，其中 dp[2][2] = 1，nk = min(3, 2 + 3) = 3，于是 dp[3][4] += 1——这是「两个项目都选」，用 $4$ 人、利润 $5$ 封顶为 $3$。j = 2 时读 dp[k][0]，其中 dp[0][0] = 1，nk = min(3, 0 + 3) = 3，于是 dp[3][2] += 1——这是「只选第二个项目」，用 $2$ 人、利润 $3$。最后求和：dp[3][2] = 1、dp[3][4] = 1，其余为 $0$，答案 $2$。验证一下：只选项目二（利润 $3 \ge 3$）和两个都选（利润 $5 \ge 3$）确实是仅有的两种方案，只选项目一利润只有 $2$ 不达标，与期望完全一致。

代码实现

class Solution {
    private static final int MOD = 1_000_000_007;

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][] dp = new int[minProfit + 1][n + 1];
        dp[0][0] = 1;

        for (int i = 0; i < group.length; i++) {
            int g = group[i];
            int p = profit[i];
            for (int j = n; j >= g; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    int nk = Math.min(minProfit, k + p);
                    dp[nk][j] = (dp[nk][j] + dp[k][j - g]) % MOD;
                }
            }
        }

        int answer = 0;
        for (int j = 0; j <= n; j++) {
            answer = (answer + dp[minProfit][j]) % MOD;
        }
        return answer;
    }
}

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
    const mod = 1_000_000_007
    dp := make([][]int, minProfit+1)
    for i := 0; i <= minProfit; i++ {
        dp[i] = make([]int, n+1)
    }
    dp[0][0] = 1

    for i := 0; i < len(group); i++ {
        g := group[i]
        p := profit[i]
        for j := n; j >= g; j-- {
            for k := minProfit; k >= 0; k-- {
                nk := k + p
                if nk > minProfit {
                    nk = minProfit
                }
                dp[nk][j] = (dp[nk][j] + dp[k][j-g]) % mod
            }
        }
    }

    answer := 0
    for j := 0; j <= n; j++ {
        answer = (answer + dp[minProfit][j]) % mod
    }
    return answer
}

复杂度分析

时间复杂度：$O(g \cdot n \cdot P)$，其中 $g$ 是项目数、$n$ 是员工数上限、$P$ 是 minProfit。三重循环各自扫一遍对应维度，最内层只做一次取小、一次加法和一次取模，都是常数时间。三者上限都是 $100$，总量约 $10^6$，运行时间在毫秒级。

空间复杂度：$O(n \cdot P)$。二维表大小是 $(P+1)(n+1)$，约 $10^4$ 个 int；物品维已经通过「原地逆序更新」滚动掉了，不需要第三维，这正是逆序遍历带来的空间收益。

关键点总结

约束「有上限」和「有下限」要用不同手法处理。人数是上限型，用常规背包维即可；利润是下限型，直接开真实值会让状态爆炸，正确做法是封顶合并——把所有「已达标」的情形压成同一个状态，用 $\min(P, k + p)$ 实现。这个技巧在「至少凑出 K 个」「覆盖度不小于 T」类计数题里通用。

0-1 背包压成一维（本题是压掉物品维）时，容量维必须逆序。判断依据是「本轮读取的值是否可能已被本轮写过」；逆序时读的下标恒小于写的下标，因此读到的一定是上一轮的值。正序则退化成完全背包，是最经典的翻车点。

计数型 DP 的初始状态是「空方案算一种」，即 dp[0][0] = 1；求最值型 DP 的初始状态才是 $0$ 或负无穷。这两类的初始化语义完全不同，混用会导致整张表恒为 $0$ 或答案凭空多出无效方案。

状态定义写「恰好」还是「至多」，决定了最后如何取答案。本题人数维定义为「恰好用 j 人」，所以要对 j 求和；若定义成「至多用 j 人」则直接取 dp[P][n] 即可。两种都对，但必须与转移和取答案的方式保持一致。

取模要在每一次加法后立刻做，而不是最后统一做。方案数会迅速超过 int 范围，延后取模必然溢出。

面试视角：字节和阿里考这题是想看能否识别出「双维度背包 + 下限封顶」这个组合。理想的作答顺序是：先说「每个项目选或不选，是 0-1 背包」，再说「有人数和利润两个约束，所以状态是二维」，最关键的一句是「利润只关心是否达标，可以在 minProfit 处封顶」。写完主动解释「为什么人数维要逆序」和「为什么最后要对人数求和」，基本就答满了。如果被追问空间优化，可以提「利润维也能滚动，但因为封顶后本就只有 $P+1$ 格，收益有限」。

易错点总结

错误写法：人数维正序遍历，写成 for (int j = g; j <= n; j++) → 用例 n = 4，minProfit = 2，group = [2]，profit = [2] → dp[2][2] 被本轮更新后又被 j = 4 读到，产生「同一个项目选两次」的方案，答案变成 $2$，正确答案是 $1$。

错误写法：忘记 dp[0][0] = 1 或初始化成 dp[0][0] = 0 → 用例任意输入 → 整张表始终为 $0$，最终答案恒为 $0$。

错误写法：不做利润封顶，直接写 dp[k + p][j] += dp[k][j - g] → 用例 minProfit = 3，profit = [5] → k + p = 5 超出数组第一维上界，数组越界异常；即便开到 $10^4$，最后也要遍历 k 从 minProfit 到最大利润求和，写漏就少算。

错误写法：封顶写成 if (k + p >= minProfit) continue; 而不是归并 → 用例 n = 5，minProfit = 3，group = [2]，profit = [3] → 唯一达标的方案被跳过，答案是 $0$，正确答案是 $1$。

错误写法：最后只取 dp[minProfit][n] 而不对人数求和 → 用例 n = 5，minProfit = 3，group = [2, 2]，profit = [2, 3] → dp[3][5] 是 $0$（没有恰好用 $5$ 人的方案），返回 $0$，正确答案是 $2$。

错误写法：把项目循环放在内层，写成 for j -> for k -> for i → 用例 n = 4，minProfit = 2，group = [2, 2]，profit = [1, 1] → 同一个 (j, k) 状态会被多个项目反复叠加，同一项目在不同人数下被重复决策，方案数远大于正确值。

错误写法：转移写成赋值 dp[nk][j] = dp[k][j - g] 而不是累加 → 用例 minProfit = 2，profit = [2, 3]，两个项目都能让利润封顶 → 后一个 k 的结果覆盖前一个，dp[minProfit][j] 只保留最后一次的值，方案数少算。

错误写法：只在最后对答案取模，中间不取 → 用例项目数接近 $100$ 且大量方案达标 → 方案数远超 $2^{31}$，int 溢出成负数，最终结果错误；每一步加法后都必须取模。

错误写法：人数维下界写成 j >= 0 而不是 j >= g → 用例 group = [3]，j = 1 → 访问 dp[k][1 - 3] 即下标 $-2$，数组越界。

错误写法：认为「利润为 0 的项目可以直接跳过」 → 用例 n = 2，minProfit = 0，group = [1]，profit = [0] → 跳过后只剩空集一种方案，返回 $1$，但选与不选是两种不同方案，正确答案是 $2$。

相似题目

题目	难度	考察点
474. 一和零	中等	同为双维度 0-1 背包，但两维都是上限型，不需要封顶合并
416. 分割等和子集	中等	单维背包且求可行性而非计数，是理解「逆序遍历」的最短入门题
494. 目标和	中等	同为计数型背包，先要把正负号问题转化成子集和，考察建模而非状态压缩
1049. 最后一块石头的重量 II	中等	求的是最接近半和的可行值，转移取最值而非累加，初始化语义与本题相反
518. 零钱兑换 II	中等	计数型完全背包，容量维必须正序，与本题的逆序正好构成对照