LeetCode 879: Profitable Schemes

Problem Restatement

We are given n gang members and several crimes.

Each crime i has:

Each member can participate in at most one crime.

A scheme is profitable if:

1. It uses at most n members.
2. It earns at least minProfit profit.

Return the number of profitable schemes modulo 10^9 + 7. The official constraints allow up to 100 members, 100 crimes, and minProfit <= 100.

Input and Output

Function shape:

def profitableSchemes(
    self,
    n: int,
    minProfit: int,
    group: list[int],
    profit: list[int]
) -> int:
    ...

Examples

Example 1:

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2

There are two valid schemes:

So the answer is 2.

Example 2:

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7

Every non-empty subset has profit at least 5, and all subsets fit within 10 members.

There are 7 non-empty subsets, so the answer is 7.

First Thought: Enumerate All Subsets

Each crime can be either chosen or skipped.

If there are m crimes, then there are:

2^m

possible subsets.

For each subset, we could compute:

total members used
total profit earned

Then count the subsets where:

members <= n and profit >= minProfit

This is correct, but it is too slow because group.length can be up to 100.

Key Insight

This is a 0/1 knapsack problem with two state dimensions:

1. Members used.
2. Profit earned.

We do not need to track profit above minProfit exactly.

Once a scheme reaches minProfit, any larger profit is equivalent for counting purposes. So we cap profit at minProfit.

For example, if minProfit = 5, then profits 5, 6, 10, and 100 are all stored as state 5.

This keeps the DP table small.

DP Definition

Let:

dp[people][earned]

be the number of schemes that use exactly people members and earn capped profit earned.

Here:

0 <= people <= n
0 <= earned <= minProfit

The profit is capped:

new_profit = min(minProfit, earned + crime_profit)

So earned == minProfit means “at least minProfit”.

Algorithm

Start with one empty scheme:

dp[0][0] = 1

Then process each crime once.

For crime i:

members = group[i]
money = profit[i]

We update the table in reverse order.

Reverse order matters because each crime can be used only once.

For each possible current state:

people from n down to members
earned from minProfit down to 0

we add this crime:

new_people = people
old_people = people - members
new_profit = min(minProfit, earned + money)

A simpler way to write the transition is:

dp[people + members][min(minProfit, earned + money)] += dp[people][earned]

when looping people downward.

At the end, every scheme with capped profit minProfit is valid.

So the answer is:

sum(dp[people][minProfit] for people in range(n + 1))

Correctness

The DP starts with dp[0][0] = 1, representing the empty scheme. It uses zero members and earns zero profit.

When processing a crime, every existing scheme has two choices: skip the crime or take the crime.

Skipping is already represented because the old DP value remains in the table.

Taking the crime is represented by adding its required members and its profit to the current state. If the new member count is at most n, the scheme is still allowed. The profit is capped at minProfit, which is safe because the final condition only asks whether profit is at least minProfit.

The reverse loop ensures that each crime contributes at most once to any scheme. If we looped forward, a newly updated state from the current crime could be used again in the same iteration, which would count the same crime multiple times. This is exactly the standard 0/1 knapsack update rule.

After all crimes are processed, dp[people][minProfit] counts schemes that use exactly people members and earn at least minProfit profit. Summing this over all people <= n counts every valid profitable scheme exactly once.

Therefore, the algorithm returns the correct number of profitable schemes.

Complexity

Let:

m = len(group)
p = minProfit

Implementation

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

        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for members, money in zip(group, profit):
            for people in range(n - members, -1, -1):
                for earned in range(minProfit, -1, -1):
                    if dp[people][earned] == 0:
                        continue

                    new_people = people + members
                    new_profit = min(minProfit, earned + money)

                    dp[new_people][new_profit] += dp[people][earned]
                    dp[new_people][new_profit] %= MOD

        answer = 0

        for people in range(n + 1):
            answer += dp[people][minProfit]
            answer %= MOD

        return answer

Code Explanation

We define the modulo:

MOD = 10**9 + 7

The DP table is:

dp = [[0] * (minProfit + 1) for _ in range(n + 1)]

dp[people][earned] stores how many schemes use people members and have capped profit earned.

The empty scheme is initialized as:

dp[0][0] = 1

Then we process every crime:

for members, money in zip(group, profit):

The reverse loop over people prevents reusing the same crime more than once:

for people in range(n - members, -1, -1):

For every current profit state:

for earned in range(minProfit, -1, -1):

we compute the new state after taking this crime:

new_people = people + members
new_profit = min(minProfit, earned + money)

Then we add the number of old schemes into the new state:

dp[new_people][new_profit] += dp[people][earned]

Finally, we sum all schemes that reach capped profit minProfit:

for people in range(n + 1):
    answer += dp[people][minProfit]

These are exactly the schemes that use at most n members and earn at least minProfit.

Testing

def run_tests():
    s = Solution()

    assert s.profitableSchemes(
        5,
        3,
        [2, 2],
        [2, 3]
    ) == 2

    assert s.profitableSchemes(
        10,
        5,
        [2, 3, 5],
        [6, 7, 8]
    ) == 7

    assert s.profitableSchemes(
        1,
        1,
        [1],
        [1]
    ) == 1

    assert s.profitableSchemes(
        1,
        2,
        [1],
        [1]
    ) == 0

    assert s.profitableSchemes(
        10,
        0,
        [2, 3],
        [0, 0]
    ) == 4

    print("all tests passed")

run_tests()

Test meaning: