給定一組二進位字串陣列
strs和兩個整數m（最多的 0 的數量）和n（最多的 1 的數量），回傳最多能選幾個字串使得 0 的總數不超過m、1 的總數不超過n。
Example:
Input: strs = [“10”,“0001”,“111001”,“1”,“0”], m = 5, n = 3 Output: 4 (選 “10”, “0001”, “1”, “0”)
Intuition
TIP
二維背包問題：每個字串有兩個「重量」（0 的數量和 1 的數量），背包有兩個容量限制。
- 類似 0/1 背包，但有兩個維度的容量限制
dp[i][j]表示最多用i個 0 和j個 1 時能選的最大字串數- 對每個字串，逆序更新 DP 表
Approaches
1. 3D DP — O(k * m * n) / O(k * m * n)
- Idea:
dp[k][i][j]表示考慮前k個字串，使用最多i個 0 和j個 1 的最大子集大小。 - Time:
O(k * m * n)，k為字串數量 - Space:
O(k * m * n)
class Solution {
fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {
val k = strs.size
val dp = Array(k + 1) { Array(m + 1) { IntArray(n + 1) } }
for (idx in 1..k) {
val zeros = strs[idx - 1].count { it == '0' }
val ones = strs[idx - 1].length - zeros
for (i in 0..m) {
for (j in 0..n) {
dp[idx][i][j] = dp[idx - 1][i][j]
if (i >= zeros && j >= ones) {
dp[idx][i][j] = maxOf(dp[idx][i][j], dp[idx - 1][i - zeros][j - ones] + 1)
}
}
}
}
return dp[k][m][n]
}
}⭐ 2. 2D DP (Space Optimized) — O(k * m * n) / O(m * n)
- Idea: 壓縮掉字串維度，逆序遍歷容量以保證每個字串只使用一次。
- Time:
O(k * m * n) - Space:
O(m * n)
class Solution {
fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {
val dp = Array(m + 1) { IntArray(n + 1) }
for (s in strs) {
val zeros = s.count { it == '0' }
val ones = s.length - zeros
for (i in m downTo zeros) {
for (j in n downTo ones) {
dp[i][j] = maxOf(dp[i][j], dp[i - zeros][j - ones] + 1)
}
}
}
return dp[m][n]
}
}🔑 Takeaways
- Pattern: 二維 0/1 背包 — 兩個容量限制，物品價值為 1
- Key trick: 逆序遍歷兩個維度的容量；本質上是 0/1 背包的擴展，只是多了一個維度