#879

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Profitable Schemes

Given a group of members and a list of crimes, count the profitable schemes that meet the profit and group constraints.

Problem Statement

You are given a group of n members and a list of crimes, where each crime has a required group size and a generated profit. A member can only participate in one crime, and the goal is to find how many subsets of crimes meet the following criteria: the total number of participants does not exceed n, and the total profit is at least minProfit.

Return the number of valid schemes modulo $10^9 + 7$ . A scheme is valid if the total participants are within the group size and the profit is greater than or equal to the specified minimum profit. This problem emphasizes efficient calculation with dynamic programming, particularly using a state transition approach.

Examples

Example 1

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

Output: 2

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

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).

Constraints

1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

Solution Approach

State Transition Dynamic Programming

This problem can be solved using dynamic programming by maintaining a 3D DP array. Each state in the DP table will track the number of schemes based on the number of crimes chosen, the group size used, and the profit accumulated. By iterating over each crime and updating the DP table, we can count valid schemes that meet the required conditions.

Dynamic State Updates

At each step, we consider whether to include or exclude a given crime. If a crime is included, we update the number of schemes based on the previous states, considering both the profit and the group size. This dynamic state update ensures that we efficiently count all combinations without having to generate all subsets directly.

Modulo Operation

Given that the number of schemes could be very large, we must return the result modulo $10^9 + 7$ . Each state update and final answer calculation must respect this modulo constraint to ensure the output is within the required range.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity of the solution depend on the DP table's dimensions. With n members, minProfit profit target, and group.length number of crimes, the space complexity is O(n * minProfit * group.length), and the time complexity is O(n * minProfit * group.length). This ensures that the solution is efficient for the given constraints.

What Interviewers Usually Probe

Assess the candidate's understanding of dynamic programming techniques, especially state transition methods.
Evaluate the candidate's ability to handle modulo operations and large numbers in dynamic programming.
Check how well the candidate optimizes space complexity while managing a DP table for this type of problem.

Common Pitfalls or Variants

Common pitfalls

Forgetting to apply the modulo $10^9 + 7$ when updating the DP table or returning the result.
Incorrectly updating the DP table when considering the number of group members for each crime.
Not handling edge cases where no valid schemes meet the profit condition.

Follow-up variants

Increased complexity when adding more crimes and larger group sizes, requiring more sophisticated dynamic programming approaches.
Modifications where the number of crimes can exceed the group size, requiring different combinatorial handling.
Extension to include specific constraints on which crimes can be paired based on external conditions.

FAQ

What is the main algorithmic technique used in Profitable Schemes?

The problem primarily uses state transition dynamic programming to efficiently count the number of valid schemes.

How can I optimize space complexity in this problem?

To optimize space, you can reduce the dimensions of the DP table, potentially using only a 2D table or a rolling array approach.

What are the edge cases to consider in Profitable Schemes?

Edge cases include scenarios where no valid schemes can be formed, and ensuring the modulo operation is applied consistently.

What role does the modulo operation play in the solution?

The modulo operation ensures that the result stays within the problem's constraints and avoids overflow due to large numbers.

How does the dynamic programming approach help in solving Profitable Schemes?

Dynamic programming helps by breaking down the problem into manageable subproblems, allowing efficient tracking of group sizes and profits across multiple crime combinations.

terminal

Solution

Solution 1: recursion with memoization

We design a function $dfs(i, j, k)$, which means that we start from the $i$-th job, and have chosen $j$ employees, and the current profit is $k$, then the number of schemes in this case is $dfs(0, 0, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def profitableSchemes(
        self, n: int, minProfit: int, group: List[int], profit: List[int]
    ) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i >= len(group):
                return 1 if k == minProfit else 0
            ans = dfs(i + 1, j, k)
            if j + group[i] <= n:
                ans += dfs(i + 1, j + group[i], min(k + profit[i], minProfit))
            return ans % (10**9 + 7)

        return dfs(0, 0, 0)

Solution 2: Dynamic Programming

We define $f[i][j][k]$ to be the number of schemes to make a profit of at least $k$ with $i$ jobs and $j$ workers. Initially, we have $f[0][j][0] = 1$, which means that there is only one scheme to make a profit of $0$ without any jobs.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def profitableSchemes(
        self, n: int, minProfit: int, group: List[int], profit: List[int]
    ) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i >= len(group):
                return 1 if k == minProfit else 0
            ans = dfs(i + 1, j, k)
            if j + group[i] <= n:
                ans += dfs(i + 1, j + group[i], min(k + profit[i], minProfit))
            return ans % (10**9 + 7)

        return dfs(0, 0, 0)

Continue Practicing

#877 stone game #873 length of longest fibonacci subsequence #871 minimum number of refueling stops