⚡Flashcard Drill➔
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

  1. Let dp[j][p] be the number of schemes using exactly j members with profit capped at p. The base is dp[0][0] = 1.
  2. 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).
  3. Capping at minProfit keeps the profit dimension small and avoids tracking unbounded sums.
  4. The answer sums dp[j][minProfit] over all j, 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 and max(0, cur - p) handles the overflow.
  • Iterating j and cur upward: 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 all j.
  • 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems