LeetCode Solutions

			

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] := # of schemes w/ first k crimes, AT MOST i members, and at
    // Least 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 # 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];
  }
};

			

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];
  }
}

			

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] := # of schemes w/ AT MOST i members and at least 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];
  }
};