NeetCode #748LC-879Hard2-D Dynamic Programming
← Back to All Problems#748 · #879 · Profitable Schemes(盈利计划)
📌 Problem Statement & Constraints
There are
n members available. Crime i needs group[i] members and yields profit[i]. Choose a subset of crimes whose total members is at most n and whose total profit is at least minProfit. Return the number of such schemes modulo 1e9+7. Constraints: 1 <= n <= 100, 0 <= minProfit <= 100, 1 <= group.length <= 100, 0 <= group[i] <= 100, 0 <= profit[i] <= 100.💡 Core Algorithmic Approaches
- Let
dp[j][p]be the number of schemes using exactlyjmembers with profit capped atp. The base isdp[0][0] = 1. - Process crimes one by one as a 0/1 knapsack: including crime
(g, p)moves from(j - g, max(0, cur - p))to(j, cur). - Capping at
minProfitkeeps the profit dimension small and avoids tracking unbounded sums. - The answer sums
dp[j][minProfit]over allj, since any member count is acceptable and the cap means the profit reached the goal.
💻 Benchmark Python3 Implementation
class Solution:
def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
MOD = 10**9 + 7
# dp[j][p] = schemes with j members and profit capped at p
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): # descending: 0/1 knapsack
for cur in range(minProfit, -1, -1):
prev = max(0, cur - p) # cap the profit dimension
dp[j][cur] = (dp[j][cur] + dp[j - g][prev]) % MOD
return sum(dp[j][minProfit] for j in range(n + 1)) % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(len(group) * n * minProfit): each crime updates the whole (members, profit) table.
💾 Space Complexity
O(n * minProfit): the 2-D table.
⚠️ Interview Pitfalls & Follow-ups
- Tracking exact profit instead of capping: profits can exceed
minProfit, so the dimension is capped andmax(0, cur - p)handles the overflow. - Iterating
jandcurupward: a 0/1 knapsack needs descending loops, or the same crime is counted multiple times. - Answering
dp[n][minProfit]: any member count is allowed, so sum over allj. - Forgetting the modulo: the number of schemes is huge.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.