# LeetCode 879: Profitable Schemes

## Problem Restatement

We are given `n` gang members and several crimes.

Each crime `i` has:

| Array | Meaning |
|---|---|
| `group[i]` | Number of members needed for crime `i` |
| `profit[i]` | Profit gained from crime `i` |

Each member can participate in at most one crime.

A scheme is profitable if:

1. It uses at most `n` members.
2. It earns at least `minProfit` profit.

Return the number of profitable schemes modulo `10^9 + 7`. The official constraints allow up to `100` members, `100` crimes, and `minProfit <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n`, `minProfit`, `group`, `profit` |
| Output | Number of valid schemes |
| Member limit | Total members used must be `<= n` |
| Profit condition | Total profit must be `>= minProfit` |
| Modulo | `10^9 + 7` |

Function shape:

```python
def profitableSchemes(
    self,
    n: int,
    minProfit: int,
    group: list[int],
    profit: list[int]
) -> int:
    ...
```

## Examples

Example 1:

```text
Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
```

There are two valid schemes:

| Crimes chosen | Members used | Profit | Valid |
|---|---:|---:|---|
| `[0]` | 2 | 2 | No |
| `[1]` | 2 | 3 | Yes |
| `[0,1]` | 4 | 5 | Yes |

So the answer is `2`.

Example 2:

```text
Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
```

Every non-empty subset has profit at least `5`, and all subsets fit within `10` members.

There are `7` non-empty subsets, so the answer is `7`.

## First Thought: Enumerate All Subsets

Each crime can be either chosen or skipped.

If there are `m` crimes, then there are:

```text
2^m
```

possible subsets.

For each subset, we could compute:

```text
total members used
total profit earned
```

Then count the subsets where:

```text
members <= n and profit >= minProfit
```

This is correct, but it is too slow because `group.length` can be up to `100`.

## Key Insight

This is a 0/1 knapsack problem with two state dimensions:

1. Members used.
2. Profit earned.

We do not need to track profit above `minProfit` exactly.

Once a scheme reaches `minProfit`, any larger profit is equivalent for counting purposes. So we cap profit at `minProfit`.

For example, if `minProfit = 5`, then profits `5`, `6`, `10`, and `100` are all stored as state `5`.

This keeps the DP table small.

## DP Definition

Let:

```text
dp[people][earned]
```

be the number of schemes that use exactly `people` members and earn capped profit `earned`.

Here:

```text
0 <= people <= n
0 <= earned <= minProfit
```

The profit is capped:

```python
new_profit = min(minProfit, earned + crime_profit)
```

So `earned == minProfit` means “at least `minProfit`”.

## Algorithm

Start with one empty scheme:

```python
dp[0][0] = 1
```

Then process each crime once.

For crime `i`:

```python
members = group[i]
money = profit[i]
```

We update the table in reverse order.

Reverse order matters because each crime can be used only once.

For each possible current state:

```python
people from n down to members
earned from minProfit down to 0
```

we add this crime:

```python
new_people = people
old_people = people - members
new_profit = min(minProfit, earned + money)
```

A simpler way to write the transition is:

```python
dp[people + members][min(minProfit, earned + money)] += dp[people][earned]
```

when looping `people` downward.

At the end, every scheme with capped profit `minProfit` is valid.

So the answer is:

```python
sum(dp[people][minProfit] for people in range(n + 1))
```

## Correctness

The DP starts with `dp[0][0] = 1`, representing the empty scheme. It uses zero members and earns zero profit.

When processing a crime, every existing scheme has two choices: skip the crime or take the crime.

Skipping is already represented because the old DP value remains in the table.

Taking the crime is represented by adding its required members and its profit to the current state. If the new member count is at most `n`, the scheme is still allowed. The profit is capped at `minProfit`, which is safe because the final condition only asks whether profit is at least `minProfit`.

The reverse loop ensures that each crime contributes at most once to any scheme. If we looped forward, a newly updated state from the current crime could be used again in the same iteration, which would count the same crime multiple times. This is exactly the standard 0/1 knapsack update rule.

After all crimes are processed, `dp[people][minProfit]` counts schemes that use exactly `people` members and earn at least `minProfit` profit. Summing this over all `people <= n` counts every valid profitable scheme exactly once.

Therefore, the algorithm returns the correct number of profitable schemes.

## Complexity

Let:

```text
m = len(group)
p = minProfit
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n * p)` | For each crime, we scan member and profit states |
| Space | `O(n * p)` | We store a 2D DP table |

## Implementation

```python
class Solution:
    def profitableSchemes(
        self,
        n: int,
        minProfit: int,
        group: list[int],
        profit: list[int]
    ) -> int:
        MOD = 10**9 + 7

        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for members, money in zip(group, profit):
            for people in range(n - members, -1, -1):
                for earned in range(minProfit, -1, -1):
                    if dp[people][earned] == 0:
                        continue

                    new_people = people + members
                    new_profit = min(minProfit, earned + money)

                    dp[new_people][new_profit] += dp[people][earned]
                    dp[new_people][new_profit] %= MOD

        answer = 0

        for people in range(n + 1):
            answer += dp[people][minProfit]
            answer %= MOD

        return answer
```

## Code Explanation

We define the modulo:

```python
MOD = 10**9 + 7
```

The DP table is:

```python
dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
```

`dp[people][earned]` stores how many schemes use `people` members and have capped profit `earned`.

The empty scheme is initialized as:

```python
dp[0][0] = 1
```

Then we process every crime:

```python
for members, money in zip(group, profit):
```

The reverse loop over `people` prevents reusing the same crime more than once:

```python
for people in range(n - members, -1, -1):
```

For every current profit state:

```python
for earned in range(minProfit, -1, -1):
```

we compute the new state after taking this crime:

```python
new_people = people + members
new_profit = min(minProfit, earned + money)
```

Then we add the number of old schemes into the new state:

```python
dp[new_people][new_profit] += dp[people][earned]
```

Finally, we sum all schemes that reach capped profit `minProfit`:

```python
for people in range(n + 1):
    answer += dp[people][minProfit]
```

These are exactly the schemes that use at most `n` members and earn at least `minProfit`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.profitableSchemes(
        5,
        3,
        [2, 2],
        [2, 3]
    ) == 2

    assert s.profitableSchemes(
        10,
        5,
        [2, 3, 5],
        [6, 7, 8]
    ) == 7

    assert s.profitableSchemes(
        1,
        1,
        [1],
        [1]
    ) == 1

    assert s.profitableSchemes(
        1,
        2,
        [1],
        [1]
    ) == 0

    assert s.profitableSchemes(
        10,
        0,
        [2, 3],
        [0, 0]
    ) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 5`, `minProfit = 3` | Standard example |
| `n = 10`, `minProfit = 5` | Counts many valid subsets |
| One valid crime | Minimum useful case |
| One insufficient crime | Profit condition fails |
| `minProfit = 0` | Every subset that fits is profitable |