# Profitable Schemes
**Difficulty:** HARD
[External](https://leetcode.com/problems/profitable-schemes)
Canonical: https://scaleengineer.com/dsa/problems/profitable-schemes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
There is a group of `n` members, and a list of various crimes they could commit. The `ith` crime generates a `profit[i]` and requires `group[i]` members to participate in it. If a 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 `minProfit` profit, and the total number of members participating in that subset of crimes is at most `n`.

Return the number of schemes that can be chosen. Since the answer may be very large, **return it modulo** `109 + 7`.

**Example 1:**

**Input:** n = 5, minProfit = 3, group = [2,2], profit = [2,3]
**Output:** 2
**Explanation:** To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

**Example 2:**

**Input:** n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
**Output:** 7
**Explanation:** To make a profit of at least 5, the group 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).

**Constraints:**

* `1 <= n <= 100`
* `0 <= minProfit <= 100`
* `1 <= group.length <= 100`
* `1 <= group[i] <= 100`
* `profit.length == group.length`
* `0 <= profit[i] <= 100`

# Approaches
## Brute Force with Backtracking
This approach explores all possible subsets of crimes. We can use a recursive backtracking function to generate every combination. For each combination, we calculate the total profit and the total number of members required. If the combination meets the criteria (profit >= `minProfit` and members <= `n`), we count it as a valid scheme.
**Time:** O(2^C), where `C` is the number of crimes (`group.length`). For each crime, we have two choices (include or exclude), leading to an exponential number of paths. · **Space:** O(C), where `C` is the number of crimes. This is for the recursion call stack depth.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
We define a recursive helper function, say `solve(index, currentProfit, currentMembers)`. This function explores all possibilities by either including or excluding each crime one by one.

- `index`: The index of the crime we are currently considering.
- `currentProfit`: The accumulated profit from the crimes chosen so far.
- `currentMembers`: The total number of members required for the crimes chosen so far.

The function works as follows:
1.  **Base Case:** When we have considered all the crimes (`index == group.length`), we check if the current scheme is profitable. If `currentProfit >= minProfit`, we have found one valid scheme.
2.  **Recursive Step:** For each crime at `index`, we have two choices:
    a. **Exclude the crime:** We move to the next crime without changing `currentProfit` or `currentMembers`.
    b. **Include the crime:** We add the crime's profit and required members to our current totals, but only if the total members do not exceed `n`.

The total number of profitable schemes is the sum of valid schemes found down all recursive paths. This approach is too slow because it explores `2^C` possibilities, where `C` is the number of crimes.

```java
// This is a conceptual example. A direct implementation would time out.
// A correct implementation would return counts from the recursion and handle modulo arithmetic.
class Solution {
    private int count = 0;

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        solve(0, 0, 0, n, minProfit, group, profit);
        return count;
    }

    private void solve(int index, int currentProfit, int currentMembers, int n, int minProfit, int[] group, int[] profit) {
        if (currentMembers > n) {
            return; // Prune this path
        }
        if (index == group.length) {
            if (currentProfit >= minProfit) {
                count++;
            }
            return;
        }

        // Option 1: Don't commit the current crime
        solve(index + 1, currentProfit, currentMembers, n, minProfit, group, profit);

        // Option 2: Commit the current crime
        solve(index + 1, currentProfit + profit[index], currentMembers + group[index], n, minProfit, group, profit);
    }
}
```
### Algorithm
- Define a recursive function `solve(index, currentProfit, currentMembers)`.
- **Base Case:** If `index` reaches the end of the crimes list (`group.length`):
    - If `currentProfit >= minProfit`, it's a valid scheme, so return 1.
    - Otherwise, return 0.
- **Recursive Step:** For the crime at `index`, there are two choices:
    1. **Exclude the crime:** Recursively call `solve(index + 1, currentProfit, currentMembers)`.
    2. **Include the crime:** If `currentMembers + group[index] <= n`, recursively call `solve(index + 1, currentProfit + profit[index], currentMembers + group[index])`.
- The total number of schemes is the sum of the results from these two choices.
- The initial call is `solve(0, 0, 0)`.

## Top-Down DP with Memoization
The brute-force approach recomputes the same subproblems multiple times. For example, the number of ways to achieve a certain profit with a certain number of members from crime `i` onwards is independent of how we reached that state. We can optimize this by storing the results of subproblems in a memoization table (a multi-dimensional array) and reusing them. This is a classic top-down dynamic programming technique.
**Time:** O(C * N * P). Each state `(index, members, profit)` is computed only once. · **Space:** O(C * N * P) for the memoization table, plus O(C) for the recursion stack. `C` is `group.length`, `N` is `n`, and `P` is `minProfit`.
**Pros:** Significantly more efficient than brute force.; Guaranteed to find the correct solution within the time limits for the given constraints.
**Cons:** Uses a large amount of memory for the 3D memoization table, which might be a concern for larger constraints.
### Explanation
We define a recursive function `solve(index, currentMembers, currentProfit)` which returns the number of profitable schemes from `index` to the end, given the `currentMembers` used and `currentProfit` earned so far.

The state of our DP is defined by `(index, members, profit)`.
- `index`: The current crime index we are considering.
- `members`: The number of members used so far.
- `profit`: The profit accumulated so far.

To keep the state space manageable, we cap the profit at `minProfit`. Any profit equal to or greater than `minProfit` is equivalent for our goal, as we only need to know if the total profit is *at least* `minProfit`.

```java
class Solution {
    int MOD = 1_000_000_007;
    Integer[][][] memo;
    int N, minP;
    int[] G, P;

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        this.N = n;
        this.minP = minProfit;
        this.G = group;
        this.P = profit;
        this.memo = new Integer[group.length][n + 1][minProfit + 1];
        return solve(0, 0, 0);
    }

    private int solve(int index, int currentMembers, int currentProfit) {
        if (index == G.length) {
            return currentProfit >= minP ? 1 : 0;
        }

        if (memo[index][currentMembers][currentProfit] != null) {
            return memo[index][currentMembers][currentProfit];
        }

        // Option 1: Don't commit crime 'index'
        int ways = solve(index + 1, currentMembers, currentProfit);

        // Option 2: Commit crime 'index'
        if (currentMembers + G[index] <= N) {
            ways = (ways + solve(index + 1, currentMembers + G[index], Math.min(minP, currentProfit + P[index]))) % MOD;
        }

        return memo[index][currentMembers][currentProfit] = ways;
    }
}
```
### Algorithm
- Create a 3D array `memo[C][N+1][P+1]` initialized with a value indicating 'not computed' (e.g., `null` or -1). `C` is `group.length`, `N` is `n`, `P` is `minProfit`.
- Define a recursive function `solve(index, members, profit)`.
- **Base Case:** If `index == C`, we have considered all crimes. Return `1` if `profit >= minProfit`, otherwise return `0`.
- **Memoization Check:** If `memo[index][members][profit]` is not null, return the stored value.
- **Recursive Step:**
    - Calculate ways by skipping the current crime: `ways = solve(index + 1, members, profit)`.
    - If the current crime can be committed (`members + group[index] <= n`):
        - Add the ways by taking the current crime: `ways = (ways + solve(index + 1, members + group[index], min(minProfit, profit + profit[index]))) % MOD`.
- Store the result in `memo[index][members][profit]` and return it.
- The final answer is the result of the initial call `solve(0, 0, 0)`.

## Bottom-Up DP with Space Optimization
This approach is an iterative, bottom-up version of the DP solution. It avoids recursion and typically has better performance due to lower overhead. By being careful with the iteration order, we can optimize the space complexity from the 3D table of the memoized solution to a 2D table.
**Time:** O(C * N * P), where `C` is `group.length`, `N` is `n`, and `P` is `minProfit`. · **Space:** O(N * P), where `N` is `n` and `P` is `minProfit`. This is a space optimization over the 3D DP table.
**Pros:** Most efficient in terms of both time and space.; Avoids recursion overhead.
**Cons:** The logic, especially with state transitions and loop directions, can be less intuitive than the recursive approach.
### Explanation
We define a 2D DP table `dp[p][g]`, where `dp[p][g]` stores the number of ways to achieve a profit of `p` using `g` members. The profit `p` is capped at `minProfit`, so the dimensions of this table are `(minProfit + 1) x (n + 1)`. Any scheme with profit greater than or equal to `minProfit` will be counted in the `p = minProfit` state.

We iterate through each crime and update the `dp` table. For each crime, we consider how it can extend existing schemes. To ensure that each crime is used at most once per scheme, we iterate the loops for members and profit backwards. This way, when we compute `dp[...][g]`, we use values from `dp[...][g - g_i]` that were computed *before* considering the current crime.

After iterating through all crimes, `dp[minProfit][g]` will contain the total number of schemes that use `g` members and achieve a profit of *at least* `minProfit`. The final answer is the sum of these counts over all possible member counts from 0 to `n`.

```java
class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int MOD = 1_000_000_007;
        // dp[p][g] = number of schemes with profit p and g members.
        // Profit is capped at minProfit, so dp[minProfit][g] includes all schemes with profit >= minProfit.
        int[][] dp = new int[minProfit + 1][n + 1];
        dp[0][0] = 1; // Base case: one way to have 0 profit and 0 members (the empty scheme).

        for (int i = 0; i < group.length; i++) {
            int p_i = profit[i];
            int g_i = group[i];

            // Iterate backwards to use each crime at most once for a given scheme.
            for (int g = n; g >= g_i; g--) {
                for (int p = minProfit; p >= 0; p--) {
                    // A scheme with profit p and g - g_i members can be extended by adding the current crime.
                    int newProfit = Math.min(minProfit, p + p_i);
                    dp[newProfit][g] = (dp[newProfit][g] + dp[p][g - g_i]) % MOD;
                }
            }
        }

        int totalSchemes = 0;
        for (int g = 0; g <= n; g++) {
            totalSchemes = (totalSchemes + dp[minProfit][g]) % MOD;
        }
        
        return totalSchemes;
    }
}
```
### Algorithm
- Create a 2D array `dp[P+1][N+1]` initialized to 0, where `P` is `minProfit` and `N` is `n`.
- `dp[p][g]` will store the number of schemes with profit exactly `p` (capped at `P`) using `g` members.
- Initialize the base case: `dp[0][0] = 1`, representing the empty scheme with 0 profit and 0 members.
- Loop through each crime `i`:
    - Let `p_i = profit[i]` and `g_i = group[i]`.
    - To avoid using the same crime multiple times in one step, iterate the loops for members and profit backwards.
    - Loop `g` from `N` down to `g_i`.
    - Loop `p` from `P` down to `0`.
        - A scheme with profit `p` and `g - g_i` members can be extended by adding crime `i`.
        - The new profit is `new_p = min(P, p + p_i)`.
        - The new member count is `g`.
        - Update the dp table: `dp[new_p][g] = (dp[new_p][g] + dp[p][g - g_i]) % MOD`.
- After iterating through all crimes, the value `dp[P][g]` will hold the number of schemes with profit *at least* `P` using `g` members.
- The final answer is the sum of `dp[P][g]` for all `g` from `0` to `N`.

# Solutions
### Java

```java
class Solution {
public
  int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
    final int mod = (int)1 e9 + 7;
    int m = group.length;
    int[][][] f = new int[m + 1][n + 1][minProfit + 1];
    for (int j = 0; j <= n; ++j) {
      f[0][j][0] = 1;
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        for (int k = 0; k <= minProfit; ++k) {
          f[i][j][k] = f[i - 1][j][k];
          if (j >= group[i - 1]) {
            f[i][j][k] =
                (f[i][j][k] +
                 f[i - 1][j - group[i - 1]][Math.max(0, k - profit[i - 1])]) %
                mod;
          }
        }
      }
    }
    return f[m][n][minProfit];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int profitableSchemes(int n, int minProfit, vector<int> &group,
                        vector<int> &profit) {
    int m = group.size();
    int f[m + 1][n + 1][minProfit + 1];
    memset(f, 0, sizeof(f));
    for (int j = 0; j <= n; ++j) {
      f[0][j][0] = 1;
    }
    const int mod = 1e9 + 7;
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        for (int k = 0; k <= minProfit; ++k) {
          f[i][j][k] = f[i - 1][j][k];
          if (j >= group[i - 1]) {
            f[i][j][k] =
                (f[i][j][k] +
                 f[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]) %
                mod;
          }
        }
      }
    }
    return f[m][n][minProfit];
  }
};

```

### Python

```python
class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int: mod = 10 ** 9 + 7 m = len(group) f = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(m + 1)] for j in range(n + 1): f[0][j][0] = 1 for i, (x, p) in enumerate(zip(group, profit), 1): for j in range(n + 1): for k in range(minProfit + 1): f[i][j][k] = f[i - 1][j][k] if j >= x: f[i][j][k] = (f[i][j][k] + f[i - 1][j - x][max(0, k - p)]) % mod return f[m][n][minProfit]

```