Profitable Schemes: 3D Dynamic Programming

May 24, 20265 min read

leetcodeproblemharddynamic-programming

You run a gang of n members. You have a list of crimes you could commit, each requiring a certain number of members and generating a certain profit. A scheme is any subset of crimes where the total members needed does not exceed n and the total profit is at least minProfit. How many distinct profitable schemes exist? Return the count modulo 10^9 + 7.

This is LeetCode 879: Profitable Schemes, a hard DP problem that combines two classic knapsack dimensions into one. The twist that makes it tricky is counting schemes that meet a profit threshold rather than hitting an exact target.

With n=5, minProfit=3, group=[2,2], profit=[2,3], there are 2 profitable schemes: crime 1 alone (profit 3) and crimes 0+1 together (profit 5). Answer: 2.

Why this problem matters

Profitable Schemes is one of the cleanest examples of a multi-dimensional knapsack. You have two constrained resources (members and profit) and you need to count subsets that satisfy both constraints simultaneously. This pattern shows up in scheduling problems, budget allocation, and anywhere you juggle multiple limited resources.

The problem also teaches you how to handle a "greater than or equal to" constraint inside DP. Most knapsack problems ask for an exact target or a maximum value. Here, you need to count all schemes that reach at least minProfit. The trick is capping the profit dimension at minProfit, which keeps the table size manageable and collapses all "good enough" profits into one bucket.

The approach: multi-dimensional knapsack

The naive way to think about this is a 3D DP table: dp[i][j][k] where i is the number of crimes considered so far, j is the number of members used, and k is the total profit earned. But that third dimension can grow very large. The key insight is that once profit reaches minProfit, we do not care how much higher it goes. Every profit of minProfit or above is equally good.

So we cap k at minProfit. The state becomes:

dp[j][k] = number of ways to use exactly j members and earn exactly profit k, where k is clamped to min(actual_profit, minProfit).

For each crime i with group[i] members and profit[i] profit, we update the table like a 0/1 knapsack. We iterate j from n down to group[i] and k from minProfit down to 0:

dp[j][min(k + profit[i], minProfit)] += dp[j - group[i]][k]

The reverse iteration ensures each crime is used at most once. The min(k + profit[i], minProfit) capping is what keeps the profit dimension bounded.

Base case: dp[0][0] = 1 (one way to use zero members and earn zero profit: commit no crimes).

Answer: sum of dp[j][minProfit] for all j from 0 to n. This counts every combination of members that achieves at least the required profit.

The solution

def profitableSchemes(n, minProfit, group, profit):
    MOD = 10**9 + 7
    dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for g, p in zip(group, profit):
        for j in range(n, g - 1, -1):
            for k in range(minProfit, -1, -1):
                dp[j][min(k + p, minProfit)] = (
                    dp[j][min(k + p, minProfit)] + dp[j - g][k]
                ) % MOD

    return sum(dp[j][minProfit] for j in range(n + 1)) % MOD

Practice multi-dimensional knapsack with spaced repetition

Visual walkthrough

Let's trace through the example n=5, minProfit=3, group=[2,2], profit=[2,3]. The DP table has rows for members used (j=0..5) and columns for profit achieved (k=0..3, capped at minProfit).

Step 1: Base case. dp[0][0] = 1 (zero members, zero profit, one empty scheme).

Rows are members used (j=0..5). Columns are profit achieved (k=0..3, capped at minProfit). One way to use 0 members for 0 profit: do nothing.

Step 2: Process crime 0 (needs 2 members, gives profit 2).

dp[2][2] += dp[0][0] = 1. Using 2 members on crime 0 yields profit 2. We iterate j from n down to group[i] to avoid reusing the same crime.

Step 3: Process crime 1 (needs 2 members, gives profit 3).

dp[2][3] += dp[0][0] = 1 (crime 1 alone: 2 members, profit 3). dp[4][3] += dp[2][2] = 1 (both crimes: 4 members, profit capped at 3). Two new entries.

Step 4: Read the answer. Sum dp[j][minProfit] for all j.

Sum the last column (k=3): 0 + 0 + 1 + 0 + 1 + 0 = 2. There are 2 profitable schemes.

The table fills crime by crime. After processing both crimes, we sum the last column (k=3) across all rows to get the answer: 2 profitable schemes.

Complexity analysis

Metric	Value
Time	O(len(group) * n * minProfit)
Space	O(n * minProfit)

We process each crime once. For each crime, we iterate over all n * minProfit states in the 2D table. The space is O(n * minProfit) because we optimized away the crime dimension by iterating in reverse, the same trick used in the classic 0/1 knapsack.

Building blocks

This problem is built on two fundamental patterns:

0/1 Knapsack. The core structure is identical to the classic knapsack: for each item (crime), decide to include it or skip it, and update a DP table accordingly. The reverse iteration over j and k prevents an item from being used more than once. If you are comfortable with Coin Change (unbounded knapsack) and Target Sum (0/1 knapsack with two choices per item), this problem extends the same idea to two knapsack dimensions.

Profit capping. The problem asks for profit "at least minProfit", not "exactly minProfit". The standard trick is to cap the profit dimension at minProfit so that any scheme with profit 3, 4, 5, or 100 all map to the same bucket k = minProfit. This keeps the DP table small and avoids tracking profits beyond what matters. You will see this same capping technique in any DP problem with a "greater than or equal to" threshold.

Drill the knapsack pattern

Edge cases to watch for

No crimes: group and profit are empty. The only scheme is the empty set with profit 0. If minProfit is 0, the answer is 1. Otherwise, the answer is 0.
minProfit = 0: every subset of crimes that fits within n members is profitable, including the empty set. The answer can be very large.
A single crime that exceeds n: if group[i] > n, that crime can never be used. The knapsack loop naturally skips it because j never reaches group[i].
All crimes have zero profit: only schemes with minProfit = 0 qualify. The answer counts all subsets that fit within n members.
Large inputs: with up to 100 crimes, n up to 100, and minProfit up to 100, the table has at most 100 * 101 entries and we process up to 100 crimes. That is roughly 10^6 operations, well within time limits.

From understanding to recall

You have just seen how to extend the 0/1 knapsack to handle two constraints at once: a member limit and a profit threshold. The key ideas to internalize are the profit capping trick (clamp k at minProfit so the table stays bounded) and the reverse iteration order (process j and k from high to low so each crime is counted at most once).

The transition dp[j][min(k + p, minProfit)] += dp[j - g][k] is the heart of the solution. Getting the min() capping and the reverse loop direction right under pressure takes practice. Spaced repetition helps you lock in the table dimensions, the iteration order, and the capping logic until writing this from scratch feels automatic.

The multi-dimensional knapsack pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Coin Change - Classic unbounded knapsack DP
House Robber - 1D DP with skip constraints
Target Sum - 0/1 knapsack with two choices per item

Try CodeBricks free