Watch 10 video solutions for Profitable Schemes, a hard level problem involving Array, Dynamic Programming. This walkthrough by NeetCodeIO has 9,602 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.
Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.
Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3] Output: 2 Explanation: 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 Explanation: 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 <= 1000 <= minProfit <= 1001 <= group.length <= 1001 <= group[i] <= 100profit.length == group.length0 <= profit[i] <= 100Problem Overview: You are given a set of crimes where each crime requires a certain number of members and generates some profit. With at most n members available, count how many subsets of crimes generate at least minProfit. Each crime can be chosen once, and the answer must be returned modulo 1e9 + 7.
Approach 1: Brute Force Subset Enumeration (Time: O(2^m), Space: O(m))
The most direct idea is to generate every subset of crimes and check whether it satisfies both constraints: total members used ≤ n and total profit ≥ minProfit. You iterate through all 2^m subsets, accumulate the group size and profit for each, and count valid schemes. This approach demonstrates the core combinatorial nature of the problem but quickly becomes infeasible when m grows (up to 100). The exponential complexity makes it unsuitable for real inputs.
Approach 2: 3D Dynamic Programming (Time: O(m * n * minProfit), Space: O(m * n * minProfit))
The key observation is that this is a constrained subset counting problem. Define a DP state dp[i][g][p] representing the number of ways to consider the first i crimes, using g members, and achieving profit p. For each crime, you either skip it or include it. When including it, update the member count and clamp profit to minProfit because anything beyond the target is equivalent for counting purposes. This transforms the exponential search into a structured dynamic programming solution over crime index, group size, and profit states. The approach is clear and systematic but consumes significant memory.
Approach 3: Space-Optimized DP (Time: O(m * n * minProfit), Space: O(n * minProfit))
The crime index dimension is unnecessary because each transition depends only on the previous state. Collapse the DP into a 2D table dp[g][p], where g is the number of members used and p is the profit achieved. Iterate through each crime and update the table in reverse order of members to avoid overwriting states needed in the same iteration. Profit is updated as newProfit = min(minProfit, p + profit[i]) so all profits beyond the threshold accumulate in the same bucket. This reduces space significantly while keeping the same time complexity. The technique is common in knapsack-style problems involving arrays and dynamic programming.
Recommended for interviews: The space-optimized DP is the expected solution. Interviewers want to see the recognition that this is a variation of the 0/1 knapsack counting problem with two constraints (members and profit). Mentioning the brute force approach shows you understand the combinatorial search space, but implementing the optimized DP demonstrates strong dynamic programming skills and awareness of state compression techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^m) | O(m) | Conceptual baseline to understand the subset search space |
| 3D Dynamic Programming | O(m * n * minProfit) | O(m * n * minProfit) | Clear DP formulation when learning the state transitions |
| Space-Optimized 2D DP | O(m * n * minProfit) | O(n * minProfit) | Optimal solution for interviews and production code |