# 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& group, vector& profit) { constexpr int kMod = 1'000'000'007; // dp[k][i][j] := # of schemes w/ first k crimes, AT MOST i members, and at // least j profits vector>> dp( group.size() + 1, vector>(n + 1, vector(minProfit + 1))); // no crimes, no profits, and any # 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 kMod = 1_000_000_007; // dp[k][i][j] := # of schemes w/ first k crimes, AT MOST i members, and at // least j profits int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1]; // no crimes, no profits, and any # 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] %= kMod; } } 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 class Solution { public: int profitableSchemes(int n, int minProfit, vector& group, vector& profit) { constexpr int kMod = 1'000'000'007; // dp[i][j] := # of schemes w/ AT MOST i members and at least j profits vector> dp(n + 1, vector(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 class Solution { public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { final int kMod = 1_000_000_007; // dp[i][j] := # of schemes w/ AT MOST i members and at least 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] %= kMod; } } return dp[n][minProfit]; } }