There is a group of n members, and a list of various crimes they could commit. The i<sup>th</sup> 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 10<sup>9</sup> + 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).

Below is a comprehensive, step-by-step guide to solve Profitable Schemes (a well-known DP problem, e.g., LeetCode #879) using the six-step approach. This problem is sometimes referred to as a variation of “0-1 Knapsack” or “Subset Sum with additional constraints.”

---

1) Explain the Problem in Simple Terms

You have:

• G: total number of group members you can use.

• P: a target profit you want to achieve (or exceed).

• Two arrays of length n (number of jobs):

  • group[i]: the number of members required to do job i.

  • profit[i]: the profit you earn from job i.

You can choose any subset of these jobs (possibly none or all) as long as the total group members used does not exceed G. You want your total profit to be at least P.

Question: How many different ways (subsets of jobs) are there to achieve at least P profit without exceeding G members? Since the number of ways can be very large, you’ll usually return the result modulo 10^9 + 7 (this is the standard requirement in coding platforms).

---

2) Draw the Decision Tree (High-Level)

Imagine a smaller case:

• G = 5, P = 3

• group = [2, 2, 3]

• profit = [1, 2, 2]

Conceptually, for each job, you have two choices: take it (if you can afford the members) or skip it.

A simplified decision tree might look like:

                        (Start)
                 /                   \
        Skip Job 0 (2,1)         Take Job 0 (2,1)
             / \                     /    \
       Skip Job 1 ...   Take Job 1 ...     ...
             ...

At each node:

• Track how many group members have been used so far.

• Track how much profit has been accumulated so far.

Eventually, you explore all subsets that keep usedMembers <= G. Among these, you count how many yield accProfit >= P.

However, enumerating all subsets is exponential. We’ll solve it efficiently using DP.

---

3) Recursion + Memoization (Top-Down Approach)

Idea

Define a function:

dp(i, g, p)

which returns the number of ways to achieve at least p profit using up to g group members from the first i jobs.

• Base cases:

  1. If p <= 0, that means we’ve already reached at least P profit. So from this state onward, that counts as 1 valid way (for the remainder of choices).

  2. If i == 0 (no jobs left) and p > 0, then we can’t achieve any more profit → 0 ways.

• Choices:

  1. Skip job i-1.

  2. Take job i-1 (if group[i-1] <= g) and add its profit to our total.

We memoize (i, g, p) so we don’t recompute states.

Note: Because we only care about reaching at least P profit, we often clamp the profit dimension at P. Once the profit is >= P, we treat it as exactly P for memo/dp indexing.

JavaScript (Recursive + Memoization)

const MOD = 10**9 + 7;

/**
 * Profitable Schemes: Recursion + Memoization
 * @param {number} G - Total group members available.
 * @param {number} P - Minimum profit to achieve.
 * @param {number[]} group - Array of group requirements for each job.
 * @param {number[]} profit - Array of profits for each job.
 * @return {number} Number of ways to achieve at least P profit.
 */
function profitableSchemesMemo(G, P, group, profit) {
  const n = group.length;

  // Memo object: key will be i-g-p
  // We'll clamp p so if it's >= P, it becomes P (meaning "profit >= P").
  const memo = {};

  function dfs(i, g, p) {
    // If we've reached required profit, count this as 1 valid way
    if (p >= P) {
      return 1;
    }
    // If no jobs left and we haven't reached P, no ways
    if (i === n) {
      return 0;
    }

    const key = `${i}-${g}-${p}`;
    if (key in memo) {
      return memo[key];
    }

    // Option 1: Skip the current job
    let ways = dfs(i + 1, g, p);

    // Option 2: Take the current job (if possible)
    const required = group[i];
    const gained = profit[i];
    if (required <= g) {
      ways += dfs(i + 1, g - required, Math.min(P, p + gained));
    }

    ways %= MOD;
    memo[key] = ways;
    return ways;
  }

  return dfs(0, G, 0);
}

// Example usage:
const G1 = 5, P1 = 3;
const group1 = [2, 2, 3];
const profit1 = [1, 2, 2];
console.log(profitableSchemesMemo(G1, P1, group1, profit1));

---

4) Implement the Tabulation (Bottom-Up Approach)

Idea

We create a 3D DP array, or more commonly, we optimize it to 2D:

dp[g][p] = number of ways to use up to g members to achieve exactly p profit

But since we only need the result for p >= P, we clamp p to a maximum of P.

1. Initialization:

   • dp[0][0] = 1 because there is exactly 1 way to have 0 profit using 0 group members —> by choosing no jobs.

   • dp[anything_else] = 0 initially.

2. Transition:

   • For each job i, for group capacity g from G down to group[i], for profit p from P down to 0:

     • let newProfit = Math.min(P, p + profit[i])

     • update:

         dp[g][newProfit] += dp[g - group[i]][p]
         dp[g][newProfit] %= MOD
       

     • We iterate backward so that each job is only counted once per iteration.

Finally, the total ways to achieve at least P profit is the sum of dp[g][P] for all g from 0 to G.
(But we can also store partial results in the same array and keep track of the final answer in dp[G][P], depending on the problem statement. Typically, we sum over all g because any group usage up to G is valid.)

JavaScript (Tabulation)

const MOD = 10**9 + 7;

/**
 * Profitable Schemes: Bottom-Up DP (Tabulation)
 * @param {number} G - Total group members available.
 * @param {number} P - Minimum profit to achieve.
 * @param {number[]} group - Array of group requirements for each job.
 * @param {number[]} profit - Array of profits for each job.
 * @return {number} Number of ways to achieve at least P profit.
 */
function profitableSchemesTab(G, P, group, profit) {
  // dp[g][p] = number of ways to use g members to get exactly p profit
  // We'll clamp p at P (so "p = P" means "p >= P")
  const dp = Array.from({ length: G + 1 }, () => Array(P + 1).fill(0));

  // Base case: 1 way to achieve 0 profit with 0 members (pick no jobs)
  dp[0][0] = 1;

  for (let i = 0; i < group.length; i++) {
    const gNeeded = group[i];
    const pGained = profit[i];

    // We go backwards to avoid counting the same job multiple times
    for (let g = G; g >= gNeeded; g--) {
      for (let p = P; p >= 0; p--) {
        const newProfit = Math.min(P, p + pGained);
        dp[g][newProfit] = (dp[g][newProfit] + dp[g - gNeeded][p]) % MOD;
      }
    }
  }

  // Sum all ways that achieve at least P profit: 
  // i.e., dp[g][P] for g in [0..G]
  let result = 0;
  for (let g = 0; g <= G; g++) {
    result = (result + dp[g][P]) % MOD;
  }
  return result;
}

// Example usage:
const G2 = 5, P2 = 3;
const group2 = [2, 2, 3];
const profit2 = [1, 2, 2];
console.log(profitableSchemesTab(G2, P2, group2, profit2));

---

5) Optimize Space Complexity (If Possible)

When we do a 2D approach, we are already significantly more space-efficient than a naive 3D approach. The dimension is (G+1) x (P+1).

• Space Complexity: O(G * P).

However, can we reduce it to 1D?

• If we attempt to store dp[p] for each profit, we still need to differentiate different g capacities.

• Generally, for “Knapsack-like” problems, we can reduce dimension by iterating from the back over g in place, but we still need a separate dimension for p profit states.

• So the best we can typically do is keep it as a 2D array but update in descending order of g and p.

Therefore, the standard “space-optimized” approach is already what you see in the 2D version. We can’t reduce it to strictly 1D without losing the ability to account for how many group members are used.

Hence, O(G * P) is generally the known space-optimized solution.

---

6) Time Complexity Analysis

Let:

• n = number of jobs

• G = total group members

• P = required profit

Recursion + Memoization

• We have states (i, g, p), where:

  • i can go from 0 to n

  • g can go from 0 to G

  • p can go from 0 to P

• So there are up to O(n * G * P) states.

• Each state is computed once with O(1) combination logic.

• Time Complexity = O(n * G * P)

• Space Complexity = O(n * G * P) in the memo (plus recursion stack overhead).

Tabulation

• We have a DP array dp[g][p] of size (G+1) x (P+1).

• For each of the n jobs, we iterate through G+1 values of g (in descending order) and P+1 values of p (also in descending order).

• Time Complexity = O(n * G * P)

• Space Complexity = O(G * P)

This is typical for “knapsack-like” problems.

---

Final Recap

1. Problem: Count the ways to choose subsets of jobs so that total used members ≤ G and total profit ≥ P.

2. Decision Tree: Each job is taken or skipped (exponential if naive).

3. Recursion + Memo: Define dp(i, g, p) to avoid recalculations.

4. Tabulation: Build up a 2D array dp[g][p] to represent ways to achieve exactly p profit with g members.

5. Space Optimization: We typically remain at 2D. That’s already the optimized dimension for this problem.

6. Time Complexity: O(n * G * P) for both memo and tabulation.

This DP pattern (in particular the 2D approach with clamping of profit) is a staple strategy for “Profitable Schemes” and other problems mixing constraints on used resources and minimal profit/score thresholds.