Profitable Schemes

How it works

Since each crime's DP state only depends on the next crime's state, we can reduce the 3D table to 2D. We iterate through crimes and update the table in-place. By processing member counts in reverse order, we ensure we use the previous iteration's values before overwriting them.

Steps

1. Create a 2D DP table dp[j][p] for member count j and profit p.
2. Initialize: for all j, set dp[j][minProfit] = 1.
3. Iterate i from N-1 down to 0:
   • Iterate j from n down to 0 (reverse to avoid using updated values).
   • For each profit p from 0 to minProfit:
     • Add the contribution from including the crime if we have enough members.
4. Return dp[n][0].

Complexity

• Time complexity: O(N * m * n)
• Space complexity: O(m * n)

Where N is the size of the group array, m is the given minimum profit, and n is the number of group members.

Things to watch for

Not Capping Profit at minProfit

When accumulating profit in the DP state, tracking values beyond minProfit wastes memory and causes state explosion. Any profit exceeding the threshold is functionally equivalent for counting valid schemes. Always cap the profit dimension at minProfit to reduce the state space from potentially unbounded to O(minProfit).

Forgetting the Modulo Operation

The problem requires results modulo 10^9 + 7 due to potentially huge answer values. Forgetting to apply modulo when summing the include and skip options leads to integer overflow. Apply modulo after every addition operation, not just at the end.

Incorrect Base Case Logic

The base case must return 1 when all crimes are considered AND the accumulated profit meets the threshold. A common mistake is returning 1 unconditionally or checking the wrong condition. The check p >= minProfit must happen only when i == len(group).

Off-by-One in Member Count Check

When deciding whether to include a crime, the condition should be n >= group[i] or equivalently n - group[i] >= 0. Using strict inequality n > group[i] incorrectly excludes cases where exactly enough members are available.

Iterating in Wrong Direction for Space Optimization

In the space-optimized bottom-up solution, iterating j (member count) in the wrong direction causes using updated values from the current iteration instead of the previous one. Process members from high to low to ensure correct dependency ordering.

from typing import List

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        mod = 10**9 + 7
        N = len(group)

        dp = [[0] * (minProfit + 1) for j in range(n + 2)]
        for j in range(n + 1):
            dp[j][minProfit] = 1

        for i in range(N - 1, -1, -1):
            for j in range(n, -1, -1):
                for p in range(minProfit + 1):
                    res = dp[j][p]
                    if j >= group[i]:
                        nxtP = min(profit[i] + p, minProfit)
                        res = (res + dp[j - group[i]][nxtP]) % mod
                    dp[j][p] = res

        return dp[n][0]

class Solution {
private:
    static const int MOD = 1e9 + 7;

public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int N = group.size();
        vector<vector<int>> dp(n + 2, vector<int>(minProfit + 1, 0));

        for (int j = 0; j <= n; j++) {
            dp[j][minProfit] = 1;
        }

        for (int i = N - 1; i >= 0; i--) {
            for (int j = n; j >= 0; j--) {
                for (int p = 0; p <= minProfit; p++) {
                    int res = dp[j][p];
                    if (j >= group[i]) {
                        int nxtP = min(profit[i] + p, minProfit);
                        res = (res + dp[j - group[i]][nxtP]) % MOD;
                    }
                    dp[j][p] = res;
                }
            }
        }

        return dp[n][0];
    }
};