集团里有 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 <= 1000 <= minProfit <= 1001 <= group.length <= 1001 <= group[i] <= 100profit.length == group.length0 <= profit[i] <= 100
解题思路
首先就是要理解题目在说什么，简单一点，就是让 n 名员工去加入某个计划，最后要求所有能完成的计划的总利润不小于 minProfit，此时的计划一共有多少种！
这是二维费用的 01背包问题，为什么不是完全背包问题呢❓❓❓
因为我们需要遍历每一个人，而对每个人来说，只能选一种计划， 所以就是 01背包 而不是 完全背包。所以无非就是比一维背包问题多了限定条件罢了，我们多给一个维度去表示即可！
状态表示
根据 “经验 + 题目要求”，可定义 dp[i][j][k] 表示在前 i 个计划中选，总人数不超过j，总利润不低于k，此时计划的总数。
状态转移方程
状态转移方程稍微会有些变化，因为每道题的限定条件都不一样，所以一定不要背题！
根据每个人对计划的状态，可以划分为选和不选：
初始化
当 i 为 0 的时候，也就是计划为 0，此时如果利润 k 也为 0 的话，那么表示利润是能满足要求的，说明此时这是一种选法，所以此时将 dp[0][j][0] 都初始化为 1 即可！
遍历顺序
根据状态转移方程，我们只需要满足 i 从小到大遍历即可！
返回值
根据状态表示，返回 dp[len][m][n]，其中 len 是计划数组的长度，m 为员工人数，n 为利润。
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
const int MOD = 1e9 + 7;
// dp[i][j][k]表示在前i种计划中选，总人数不超过j，总利润不低于k，此时计划的个数
// 为了与题解表示的字母联系起来，下面多做几步赋值操作
int len = group.size();
int m = n;
n = minProfit;
vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
// 初始化
for(int j = 0; j <= m; ++j)
dp[0][j][0] = 1;
for(int i = 1; i <= len; ++i)
{
for(int j = 0; j <= m; ++j)
{
for(int k = 0; k <= n; ++k)
{
dp[i][j][k] = dp[i - 1][j][k];
if(j >= group[i - 1])
dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
// 注意结果要取模
dp[i][j][k] %= MOD;
}
}
}
return dp[len][m][n];
}
};优化
所有的「背包问题」，都可以进行空间上的优化。
对于 二维费用的 01背包 类型的，我们的优化策略是：
- 删掉第一维
- 修改第二层和第三层循环的遍历顺序即可
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
const int MOD = 1e9 + 7;
// dp[i][j][k]表示在前i种计划中选，总人数不超过j，总利润不低于k，此时计划的个数
// 为了与题解表示的字母联系起来，下面多做几步赋值操作
int len = group.size();
int m = n;
n = minProfit;
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// 初始化
for(int j = 0; j <= m; ++j)
dp[j][0] = 1;
for(int i = 1; i <= len; ++i)
{
for(int j = m; j >= group[i - 1]; --j)
{
for(int k = n; k >= 0; --k)
{
dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
// 注意结果要取模
dp[j][k] %= MOD;
}
}
}
return dp[m][n];
}
};