Hard

题目描述

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名员工共同参与。如果一名员工参与了其中一项工作，就不能参与另一项工作。

我们来定义「盈利计划」：选择一部分工作，使得参与工作的员工人数最多为 n，且能够获得的利润至少为 minProfit。

返回可以获得盈利计划的方案数。答案可能很大，所以 返回答案模 10^9 + 7 的结果。

示例 1：

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1，或仅完成工作 1。
总的来说，有两种计划。

示例 2：

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

  • 1 <= n <= 100
  • 0 <= minProfit <= 100
  • 1 <= group.length <= 100
  • 1 <= group[i] <= 100
  • profit.length == group.length
  • 0 <= profit[i] <= 100

解题思路

这是一道经典的三维动态规划问题，可以看作是多约束的背包问题变种。

思路分析： 我们需要在有限的人员数量约束下，选择工作使得利润达到要求。定义状态 dp[i][j][k] 表示考虑前 i 个工作，使用恰好 j 个员工，获得恰好 k 利润的方案数。

但直接这样定义会有问题，因为我们关心的是"至少"获得 minProfit 的利润。因此，我们可以优化状态定义：dp[i][j][k] 表示考虑前 i 个工作，使用不超过 j 个员工，获得至少 k 利润的方案数。

为了避免重复计算，我们可以进一步优化：当利润超过 minProfit 时，将其视为 minProfit，因为我们只关心是否达到最低要求。

状态转移： 对于第 i 个工作，我们有两种选择：

  1. 不选择：dp[i][j][k] = dp[i-1][j][k]
  2. 选择（如果员工数量允许）：dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])]

空间优化： 由于每层转移只依赖前一层，可以使用滚动数组优化空间复杂度，将三维数组压缩为二维。

代码实现

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int MOD = 1e9 + 7;
        int m = group.size();
        
        // dp[j][k] 表示使用不超过j个员工，获得至少k利润的方案数
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1, 0));
        
        // 初始化：不工作的情况下，利润为0的方案数为1
        for (int j = 0; j <= n; j++) {
            dp[j][0] = 1;
        }
        
        for (int i = 0; i < m; i++) {
            int g = group[i], p = profit[i];
            // 从后往前遍历，避免重复使用当前工作
            for (int j = n; j >= g; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - g][max(0, k - p)]) % MOD;
                }
            }
        }
        
        return dp[n][minProfit];
    }
};

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        MOD = 10**9 + 7
        m = len(group)
        
        # dp[j][k] 表示使用不超过j个员工，获得至少k利润的方案数
        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
        
        # 初始化：不工作的情况下，利润为0的方案数为1
        for j in range(n + 1):
            dp[j][0] = 1
        
        for i in range(m):
            g, p = group[i], profit[i]
            # 从后往前遍历，避免重复使用当前工作
            for j in range(n, g - 1, -1):
                for k in range(minProfit, -1, -1):
                    dp[j][k] = (dp[j][k] + dp[j - g][max(0, k - p)]) % MOD
        
        return dp[n][minProfit]

public class Solution {
    public int ProfitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        const int MOD = 1000000007;
        int m = group.Length;
        
        // dp[j,k] 表示使用不超过j个员工，获得至少k利润的方案数
        int[,] dp = new int[n + 1, minProfit + 1];
        
        // 初始化：不工作的情况下，利润为0的方案数为1
        for (int j = 0; j <= n; j++) {
            dp[j, 0] = 1;
        }
        
        for (int i = 0; i < m; i++) {
            int g = group[i], p = profit[i];
            // 从后往前遍历，避免重复使用当前工作
            for (int j = n; j >= g; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j, k] = (dp[j, k] + dp[j - g, Math.Max(0, k - p)]) % MOD;
                }
            }
        }
        
        return dp[n, minProfit];
    }
}

var profitableSchemes = function(n, minProfit, group, profit) {
    const MOD = 1e9 + 7;
    const m = group.length;
    
    // dp[j][k] 表示使用不超过j个员工，获得至少k利润的方案数
    const dp = Array(n + 1).fill().map(() => Array(minProfit + 1).fill(0));
    
    // 初始化：不工作的情况下，利润为0的方案数为1
    for (let j = 0; j <= n; j++) {
        dp[j][0] = 1;
    }
    
    for (let i = 0; i < m; i++) {
        const g = group[i], p = profit[i];
        // 从后往前遍历，避免重复使用当前工作
        for (let j = n; j >= g; j--) {
            for (let k = minProfit; k >= 0; k--) {
                dp[j][k] = (dp[j][k] + dp[j - g][Math.max(0, k - p)]) % MOD;
            }
        }
    }
    
    return dp[n][minProfit];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m × n × minProfit)
空间复杂度O(n × minProfit)

其中 m 为工作数量，n 为员工数量，minProfit 为最小利润要求。