力扣题解（盈利计划）
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
思路：
本题由于题目要求的是利润不小于minprofit的所有计划数目，因此dp设计上有所特别。
dp[i][j][k]表示前i个工作，利润不小于j，所需工人不大于k的所有计划数目，则dp的组成：
dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-p[i]][k-g[i]],此处要求k-g[i]必须大于等于0，因为不可能存在人数小于一个负数的情况，但j-p[i]可以小于等于0，因此存在利润大于一个负数的情况，注意，这是因此此处dp的设计含义导致的。但是数组下标不能是负的，而利润正常也不会是负的，因此对于j-p[i]小于零的情况，其可能的计划数目和j位置取0的计划数目一致，因此实质上dp[i][j][k]=dp[i-1][j][k]+dp[i-1][ max(j-p[i] ,0) ][k-g[i]]。
初始化：
当j=0的时候，即求利润大于等于零的情况，则不管i，k取什么值，都至少有所有都不取这一种选择方法使得j==0成立，因此dp[0][j][0]=1.
优化：
此处dp[i][][]之和dp[i-1][][]有关，因此可以化成二维，主要这样的话j，k要从大到小遍历。
class Solution {
public:
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) {
const int mod=1e9 + 7;
int len=g.size();
vector<vector<int>>dp(n+1,vector<int>(m+1));
for(int j=0;j<=n;j++)
{
dp[j][0]=1;
}
for(int i=1;i<=len;i++)
for(int j=n;j>=g[i-1];j--)
for(int k=m;k>=0;k--)
{
dp[j][k]+=dp[j-g[i-1]][max(0,k-p[i-1])];
dp[j][k]%=mod;
}
return dp[n][m];
}
};原文地址：https://blog.csdn.net/yyssas/article/details/140589070
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！