Skip to content

879. Profitable Schemes 👍

Approach 1: 2D DP

  • Time: $O(gnp)$, where $g = |\texttt{group}|$ and $p = \texttt{minProfit}$
  • Space: $O(gnp)$, where $g = |\texttt{group}|$ and $p = \texttt{minProfit}$
 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
class Solution {
 public:
  int profitableSchemes(int n, int minProfit, vector<int>& group,
                        vector<int>& profit) {
    constexpr int kMod = 1'000'000'007;
    // dp[k][i][j] := the number of schemes, where the first k crimes are
    // committed by <= i members, generating >= j profits
    vector<vector<vector<int>>> dp(
        group.size() + 1,
        vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));

    // No crimes, no profits, and any number of members.
    for (int i = 0; i <= n; ++i)
      dp[0][i][0] = 1;

    for (int k = 1; k <= group.size(); ++k) {
      const int g = group[k - 1];
      const int p = profit[k - 1];
      for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= minProfit; ++j)
          if (i < g) {
            dp[k][i][j] = dp[k - 1][i][j];
          } else {
            dp[k][i][j] = dp[k - 1][i][j] + dp[k - 1][i - g][max(0, j - p)];
            dp[k][i][j] %= kMod;
          }
    }

    return dp[group.size()][n][minProfit];
  }
};

 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
class Solution {
  public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
    final int MOD = 1_000_000_007;
    // dp[k][i][j] := the number of schemes, where the first k crimes are
    // committed by <= i members, generating >= j profits
    int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];

    // No crimes, no profits, and any number of members.
    for (int i = 0; i <= n; ++i)
      dp[0][i][0] = 1;

    for (int k = 1; k <= group.length; ++k) {
      final int g = group[k - 1];
      final int p = profit[k - 1];
      for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= minProfit; ++j)
          if (i < g) {
            dp[k][i][j] = dp[k - 1][i][j];
          } else {
            dp[k][i][j] = dp[k - 1][i][j] + dp[k - 1][i - g][Math.max(0, j - p)];
            dp[k][i][j] %= MOD;
          }
    }

    return dp[group.length][n][minProfit];
  }
}

Approach 2: 1D DP

  • Time: $O(gnp)$
  • Space: $O(np)$
 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
class Solution {
 public:
  int profitableSchemes(int n, int minProfit, vector<int>& group,
                        vector<int>& profit) {
    constexpr int kMod = 1'000'000'007;
    // dp[i][j] := the number of schemes, where <= i members, generating
    // >= j profits
    vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));

    for (int i = 0; i <= n; ++i)
      dp[i][0] = 1;

    for (int k = 1; k <= group.size(); ++k) {
      const int g = group[k - 1];
      const int p = profit[k - 1];
      for (int i = n; i >= g; --i)
        for (int j = minProfit; j >= 0; --j) {
          dp[i][j] += dp[i - g][max(0, j - p)];
          dp[i][j] %= kMod;
        }
    }

    return dp[n][minProfit];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
    final int MOD = 1_000_000_007;
    // dp[i][j] := the number of schemes, where <= i members, generating
    // >= j profits
    int[][] dp = new int[n + 1][minProfit + 1];

    for (int i = 0; i <= n; ++i)
      dp[i][0] = 1;

    for (int k = 1; k <= group.length; ++k) {
      final int g = group[k - 1];
      final int p = profit[k - 1];
      for (int i = n; i >= g; --i)
        for (int j = minProfit; j >= 0; --j) {
          dp[i][j] += dp[i - g][Math.max(0, j - p)];
          dp[i][j] %= MOD;
        }
    }

    return dp[n][minProfit];
  }
}