leetcode-javascript/solutions/0879-profitable-schemes.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Profitable Schemes
 * Time Complexity: O(group.length * n * minProfit)
 * Space Complexity: O(n * minProfit)
 */
var profitableSchemes = function (n, minProfit, group, profit) {
  const moduloConstant = 1e9 + 7;

  const schemeCounts = Array.from({ length: n + 1 }, () =>
    new Array(minProfit + 1).fill(0),
  );

  schemeCounts[0][0] = 1;

  const totalCrimes = group.length;
  for (let crimeIndex = 0; crimeIndex < totalCrimes; crimeIndex++) {
    const requiredMembersForCrime = group[crimeIndex];
    const profitFromCrime = profit[crimeIndex];

    for (
      let currentMemberCount = n;
      currentMemberCount >= requiredMembersForCrime;
      currentMemberCount--
    ) {
      for (
        let achievedProfit = minProfit;
        achievedProfit >= 0;
        achievedProfit--
      ) {
        const previousProfitRequired = Math.max(
          0,
          achievedProfit - profitFromCrime,
        );

        schemeCounts[currentMemberCount][achievedProfit] =
          (schemeCounts[currentMemberCount][achievedProfit] +
            schemeCounts[currentMemberCount - requiredMembersForCrime][
              previousProfitRequired
            ]) %
          moduloConstant;
      }
    }
  }

  let totalProfitableSchemes = 0;
  for (let finalMemberCount = 0; finalMemberCount <= n; finalMemberCount++) {
    totalProfitableSchemes =
      (totalProfitableSchemes + schemeCounts[finalMemberCount][minProfit]) %
      moduloConstant;
  }

  return totalProfitableSchemes;
};