879. 盈利计划

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/profitable-schemes/
Star
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 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
通过次数22,158提交次数40,092

法1 动态规划 三维dp

思路
对于每一份工作，都可以有选择 或者不选择
状态定义：
dp[i][j][k]， i,j,k分别表示，选择前i个工作，且员工数量不超过j时，所创造的总利润大于等于k的计划数
状态转移：
不选择当前工作：dp[i][j][k] = dp[i-1][j][k]
选择当前工作：dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][max(0, k-profit[i-1])]
注：第二维好理解，选择了当前工作，那必然是要以一部分工人为代价的。第三维的解释：
当当前工作的利润大于 k时，那就可以直接从0开始，而没必要借助之前轮的利润。
 
题解
class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        MOD = 10**9 + 7
        # dp[i][j][k] 
        # i,j,k分别表示，选择前i个工作，且员工数量不超过j时，所创造的总利润大于等于k的计划数
        dp = [[[0] * (minProfit+1) for _ in range(n+1)] for _ in range(len(group)+1)]

        dp[0][0][0] = 1
    
        for i in range(1, len(profit)+1):
            for j in range(0, n+1):
                for k in range(0, minProfit+1):
                    # 不选择当前的工作
                    dp[i][j][k] = dp[i-1][j][k]
                    #所需的员工数量小于j，则说明可以选择当前这个工作
                    if j - group[i-1] >= 0:
                        # 前置任务所创造的利润 +第i个任务的利润要大于等于k
                        if k - profit[i-1] >= 0:
                            # 第i个任务自己的利润就已经大于等于k了，则所有前置任务的利润只需要大于等于k-earn就行, 
														# 由于利润不能为负数，所有从0开启
                            dp[i][j][k] += dp[i-1][j-group[i-1]][k - profit[i-1]]
                        else:
                            dp[i][j][k] += dp[i-1][j-group[i-1]][0]

        
        total = sum([dp[len(profit)][j][minProfit] for j in range(n + 1)]) % MOD
        return total