# Profitable Schemes

Let dp[i][g][p] to be the first i’th jobs (including) with exact g members used and having exact p profit.

``   dp[i][g][p] += dp[i - 1][g][p]``

``````if(g + group[i - 1] > G){
continue;//skip
}``````

``````if(p + profit[i - 1] > P){
dp[i][g + group[i - 1]][P] += dp[i - 1][g][p];
dp[i][g + group[i - 1]][P] %= mod;
}
``````

``````else{
dp[i][g + group[i - 1]][p + profit[i - 1]] += dp[i - 1][g][p];
dp[i][g + group[i - 1]][p + profit[i - 1]] %= mod;
}``````

``````int res = 0;
for (int i = 0; i <= G; i++) {
res += dp[n][i][P];
res %= mod;
}``````

``````class Solution {
public int profitableSchemes(int G, int P, int[] group, int[] profit) {
int mod = 1_000_000_007;
int n = group.length;
int[][][] dp = new int[n + 1][G + 1][P + 1];
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int g = 0; g <= G; g++) {
for (int p = 0; p <= P; p++) {
dp[i][g][p] += dp[i - 1][g][p];// not selected i
dp[i][g][p] %= mod;
if(g + group[i - 1] > G) // if need too many members
continue;//skip
if(p + profit[i - 1] > P){ // if it is already over profit
dp[i][g + group[i - 1]][P] += f[i - 1][g][p]; // add it to P(the target profit)
dp[i][g + group[i - 1]][P] %= mod;
}
else{
dp[i][g + group[i - 1]][p + profit[i - 1]] += dp[i - 1][g][p]; // select i as a part of the subset
dp[i][g + group[i - 1]][p + profit[i - 1]] %= mod;
}
}
}
}
int res = 0;
for (int i = 0; i <= G; i++) {
res += dp[n][i][P];
res %= mod;
}
return res;
}
}``````