101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. 3D Dynamic Programming - Complex approach
  2. 2D Dynamic Programming (Space Optimization) - Complex approach

Approach 1: 3D Dynamic Programming

The key insight for solving this problem is to use dynamic programming with three dimensions: the number of crimes considered, the number of members used, and the profit generated.

Let's define dp[i][j][k] as the number of schemes when considering the first i crimes, using exactly j members, and generating at least k profit.

For each crime, we have two options:

  1. Include the crime in our scheme.
  2. Exclude the crime from our scheme.

If we include the crime, we need to ensure that we have enough members to commit it. The recurrence relation is:

dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][max(0, k-profit[i-1])] if j >= group[i-1]

If we exclude the crime, the recurrence relation is:

dp[i][j][k] = dp[i-1][j][k]

The base case is dp[0][0][0] = 1, which means there is one way to achieve 0 profit with 0 members when considering 0 crimes (by doing nothing).

The final answer is the sum of dp[m][j][minProfit] for all j from 0 to n, where m is the number of crimes.

Algorithm:

  1. Initialize a 3D DP array dp of size (m+1) x (n+1) x (minProfit+1), where m is the number of crimes.
  2. Set dp[0][0][0] = 1 as the base case.
  3. For each crime i from 1 to m:
  4. a. For each number of members j from 0 to n:
  5. i. For each profit k from 0 to minProfit:
  6. 1. Exclude the crime: dp[i][j][k] += dp[i-1][j][k]
  7. 2. Include the crime if we have enough members: if j >= group[i-1], dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])]
  8. Calculate the final answer as the sum of dp[m][j][minProfit] for all j from 0 to n, modulo 10^9 + 7.

Time Complexity:

O(m * n * minProfit)

Where m is the number of crimes, n is the number of members, and minProfit is the minimum profit required. We need to compute dp[i][j][k] for each i from 0 to m, each j from 0 to n, and each k from 0 to minProfit.

Space Complexity:

O(m * n * minProfit)

We use a 3D DP array of size (m+1) x (n+1) x (minProfit+1).

Approach 2: 2D Dynamic Programming (Space Optimization)

We can optimize the space complexity of the previous approach by observing that we only need the results from the previous crime to calculate the results for the current crime.

Instead of using a 3D DP array, we can use a 2D DP array dp[j][k] to represent the number of schemes using exactly j members and generating at least k profit.

For each crime, we update the DP array in reverse order to avoid using the updated values in the same iteration.

The recurrence relation remains the same, but we need to be careful about the order of updates to avoid overwriting values that we still need.

Algorithm:

  1. Initialize a 2D DP array dp of size (n+1) x (minProfit+1).
  2. Set dp[0][0] = 1 as the base case.
  3. For each crime i from 0 to m-1:
  4. a. For each number of members j from n down to group[i]:
  5. i. For each profit k from minProfit down to 0:
  6. 1. Update dp[j][k] += dp[j-group[i]][max(0, k-profit[i])]
  7. Calculate the final answer as the sum of dp[j][minProfit] for all j from 0 to n, modulo 10^9 + 7.

Time Complexity:

O(m * n * minProfit)

Where m is the number of crimes, n is the number of members, and minProfit is the minimum profit required. We need to compute dp[j][k] for each crime, each j from 0 to n, and each k from 0 to minProfit.

Space Complexity:

O(n * minProfit)

We use a 2D DP array of size (n+1) x (minProfit+1).

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function profitableSchemes(n, minProfit, group, profit):
    m = length of group
 
    // Initialize 3D DP array
    dp = new 3D array of size (m+1) x (n+1) x (minProfit+1), initialized with 0
    dp[0][0][0] = 1  // Base case
 
    for i from 1 to m:
        for j from 0 to n:
            for k from 0 to minProfit:
                // Exclude the crime
                dp[i][j][k] = dp[i-1][j][k]
 
                // Include the crime if we have enough members
                if j >= group[i-1]:
                    dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])]
 
    // Calculate the final answer
    result = 0
    for j from 0 to n:
        result = (result + dp[m][j][minProfit]) % MOD
 
    return result
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone