Formatted question description: https://leetcode.ca/all/879.html

# 879. Profitable Schemes

## Level

Hard

## Description

There are G people in a gang, and a list of various crimes they could commit.

The `i`

-th crime generates a `profit[i]`

and requires `group[i]`

gang members to participate.

If a gang member participates in one crime, that member can’t participate in another crime.

Let’s call a *profitable scheme* any subset of these crimes that generates at least `P`

profit, and the total number of gang members participating in that subset of crimes is at most G.

How many schemes can be chosen? Since the answer may be very large, **return it modulo** `10^9 + 7`

.

**Example 1:**

**Input:** G = 5, P = 3, group = [2,2], profit = [2,3]

**Output:** 2

**Explanation:**

To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.

In total, there are 2 schemes.

**Example 2:**

**Input:** G = 10, P = 5, group = [2,3,5], profit = [6,7,8]

**Output:** 7

**Explanation:**

To make a profit of at least 5, the gang could commit any crimes, as long as they commit one.

There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

**Note:**

`1 <= G <= 100`

`0 <= P <= 100`

`1 <= group[i] <= 100`

`0 <= profit[i] <= 100`

`1 <= group.length = profit.length <= 100`

## Solution

Use dynamic programming. Create a 3D array `dp`

of size `(group.length + 1) * (P + 1) * (G + 1)`

, where `dp[i][j][k]`

represents the number of profitable schemes for the `i`

-th crime (1-indexed), there is already profit `j`

and there are `k`

gang members remaining. Initially, `dp[0][0][G] = 1`

.

For index `i`

, obtain `curProfit = profit[i - 1]`

and `curGroup = group[i - 1]`

, and update the elements as `dp[i][j + curProfit][k - curGroup] += dp[i - 1][j][k]`

and `dp[i][j][k] += dp[i - 1][j][k]`

. Note that if `j + curProfit > P`

, then use `P`

instead of `j + curProfit`

, and the first update is only applicable when `k - curGroup >= 0`

.

Finally, calculate the sum of all the elements in `dp[group.length][P]`

and return the sum.

```
class Solution {
public int profitableSchemes(int G, int P, int[] group, int[] profit) {
final int MODULO = 1000000007;
int length = group.length;
int[][][] dp = new int[length + 1][P + 1][G + 1];
dp[0][0][G] = 1;
for (int i = 1; i <= length; i++) {
int curProfit = profit[i - 1];
int curGroup = group[i - 1];
for (int j = 0; j <= P; j++) {
int totalProfit = Math.min(j + curProfit, P);
for (int k = 0; k <= G; k++) {
if (k >= curGroup)
dp[i][totalProfit][k - curGroup] = (dp[i][totalProfit][k - curGroup] + dp[i - 1][j][k]) % MODULO;
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % MODULO;
}
}
}
int schemes = 0;
for (int i = 0; i <= G; i++)
schemes = (schemes + dp[length][P][i]) % MODULO;
return schemes;
}
}
```