LeetCode 879. 盈利计划

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 阿里
标签
数组 动态规划

题目描述

✅ 879. 盈利计划

image-20260928225243534

image-20260928225243535

题意分析

从工作列表中选择一个子集，每项工作最多选择一次，总人数不超过 n，总利润至少为 minProfit。统计的是选择哪些工作的方案数，不是员工的具体分配方式；即使两项工作的成本和利润相同，它们仍是不同的可选工作。

解法：二维 DP

核心思路

[!blue]

令 P = minProfit。处理完前若干项工作后，dp[k][j] 表示恰好使用 j 人、封顶利润为 k 的方案数。封顶利润定义为 min(P, 实际利润)：当 k < P 时利润恰好为 k，当 k == P 时代表所有利润至少为 P 的方案。利润均非负，一旦达标，后续选择不会使它失去资格，因此无需区分超过门槛后的具体数值。

空集恰好使用 0 人、利润为 0，所以只初始化 dp[0][0] = 1。处理一项需要 g 人、利润为 p 的工作时，不选它的方案已保留在原表中；选择它则把旧状态 dp[k][j - g] 加到 dp[min(P, k + p)][j]，其中 j 是选择后的总人数。不同旧方案即使封顶到同一利润，也仍是不同子集，必须累加而不是覆盖。

为原地更新，人数 j 从 n 倒序到 g。题目保证 g >= 1，所以来源列 j - g 小于当前列，尚未在本轮更新，读取的仍是未选择当前工作的旧状态；这样每项工作只会使用一次。代码也倒序遍历利润，但防止重复选择的关键是人数倒序。即使利润为 0，或者封顶后新旧利润下标相同，来源人数仍更少，不会读到当前工作刚写出的结果。

全部工作处理完后，达标状态位于 dp[P] 这一行。由于人数维度表示恰好使用，而题目只要求不超过上限，需要累加 j = 0 到 n 的所有值。每次累加后取模，保持计数在规定范围内。

解题步骤

  1. 分配 (P + 1) × (n + 1) 的计数表，只将 dp[0][0] 设为 1。
  2. 逐项处理工作，人数从 n 倒序到 g，利润从 P 倒序到 0。
  3. 计算 nk = min(P, k + p)，执行 dp[nk][j] += dp[k][j - g] 并取模；原表中的值同时保留了不选当前工作的情况。
  4. 汇总 dp[P][0...n]。P = 0 时空集也应计入，零利润工作仍可能形成新的合法子集，不能跳过。

代码实现

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(n+1)(P+1))$，G 为项目数，P 为最低利润。
  • 空间复杂度：$O((n+1)(P+1))$。

关键点总结

[!green]

  • 人数是恰好使用，所以最后需要对所有人数求和。
  • 最低利润零时，空方案也应计入。

易错点总结

[!yellow]

  • 人数正序会重复选同一项目。
  • 达到利润上限后直接跳过，会删除全部合格方案。
  • 忽略零利润项目，会少计不同的合法子集。

相似题目

题目 难度 关联与区别
474. 一和零 中等 同样有两个容量或收益维度，本题计数并把已达利润阈值的状态合并，原题最大化选取数量。
494. 目标和 中等 同样对每个对象做选与不选的0/1计数，本题还同时限制人数并要求最低利润。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/77065409
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！