879.盈利计划

链接：879.盈利计划
难度：Hard
标签：数组、动态规划
简介：集团里有 n 名员工，他们可以完成各种各样的工作创造利润。有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

题解 1 - typescript

• 编辑时间：2021-06-09
• 执行用时：320ms
• 内存消耗：76.8MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/profitable-schemes/solution/ying-li-ji-hua-by-leetcode-solution-3t8o/)。

function profitableSchemes(
  n: number,
  minProfit: number,
  group: number[],
  profit: number[]
): number {
  const MOD = 1e9 + 7;
  const len = group.length;
  const dp = new Array(len + 1)
    .fill(0)
    .map(_ => new Array(n + 1).fill(0).map(_ => new Array(minProfit + 1).fill(0)));
  dp[0][0][0] = 1;
  for (let i = 1; i <= len; i++) {
    const member = group[i - 1];
    const earn = profit[i - 1];
    for (let j = 0; j <= n; j++) {
      for (let k = 0; k <= minProfit; k++) {
        if (j < member) {
          dp[i][j][k] = dp[i - 1][j][k];
        } else {
          dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - member][Math.max(0, k - earn)]) % MOD;
        }
      }
    }
  }
  let ans = 0;
  for (let i = 0; i <= n; i++) ans = (ans + dp[len][i][minProfit]) % MOD;
  return ans;
}