Description
有一個犯罪集團，共
n個成員。有多個犯罪計劃，第i個計劃需要group[i]個成員，能獲利profit[i]。同一個成員不能參與多個計劃。回傳能獲利至少minProfit的方案數（對 10^9+7 取餘）。
Example:
Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3] Output: 2
Intuition#
三維 0/1 背包：維度為「計劃」、「人數」、「利潤」，計算滿足最低利潤的方案數。
dp[j][k]表示使用j個成員、獲利恰好為k的方案數- 利潤維度上限為
minProfit（超過都算作minProfit，因為只要 >= 就行） - 最後答案為
dp[0..n][minProfit]的總和
Approaches#
1: 3D DP#
- 概念:
dp[i][j][k]表示考慮前i個計劃、用j個人、獲利為k的方案數。 - 時間複雜度:
O(plans * n * minProfit) - 空間複雜度:
O(plans * n * minProfit)
class Solution {
fun profitableSchemes(n: Int, minProfit: Int, group: IntArray, profit: IntArray): Int {
val MOD = 1_000_000_007L
val plans = group.size
val dp = Array(plans + 1) { Array(n + 1) { LongArray(minProfit + 1) } }
for (j in 0..n) dp[0][j][0] = 1
for (i in 1..plans) {
val g = group[i - 1]
val p = profit[i - 1]
for (j in 0..n) {
for (k in 0..minProfit) {
dp[i][j][k] = dp[i - 1][j][k]
if (j >= g) {
val prevK = maxOf(0, k - p)
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][prevK]) % MOD
}
}
}
}
var result = 0L
for (j in 0..n) result = (result + dp[plans][j][minProfit]) % MOD
return result.toInt()
}
}⭐2: 2D DP（空間優化）#
- 概念: 壓縮掉計劃維度，逆序遍歷人數和利潤。利潤超過
minProfit的統一歸到minProfit。 - 時間複雜度:
O(plans * n * minProfit) - 空間複雜度:
O(n * minProfit)
class Solution {
fun profitableSchemes(n: Int, minProfit: Int, group: IntArray, profit: IntArray): Int {
val MOD = 1_000_000_007L
val dp = Array(n + 1) { LongArray(minProfit + 1) }
for (j in 0..n) dp[j][0] = 1
for (i in group.indices) {
val g = group[i]
val p = profit[i]
for (j in n downTo g) {
for (k in minProfit downTo 0) {
val newK = minOf(k + p, minProfit)
dp[j][newK] = (dp[j][newK] + dp[j - g][k]) % MOD
}
}
}
return dp[n][minProfit].toInt()
}
}🔑 Takeaways#
- Pattern: 多維 0/1 背包 — 人數和利潤兩個限制
- 關鍵技巧: 利潤超過目標的統一歸類為
minProfit，避免陣列過大；逆序遍歷是 0/1 背包的標準技巧