題目描述:
給定一個二進位字串陣列 strs,以及兩個整數 m 和 n。從 strs 中選出一個最大的子集,使得子集中所有字串的 0 的總數不超過 m,1 的總數不超過 n。回傳最大子集的大小。
解題思路: 這是一個二維背包問題(0/1 Knapsack 的變體)。每個字串是一個「物品」,有兩個維度的「重量」(0 的數量和 1 的數量),「價值」為 1(選入子集)。
定義 dp[i][j] = 使用最多 i 個 0 和 j 個 1 時能選的最多字串數。
對每個字串(含 zeros 個 0 和 ones 個 1):
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)最終答案為 dp[m][n]。
時間複雜度:O(l * m * n) — l 為字串數量,對每個字串更新 m * n 的 DP 表。
空間複雜度:O(m * n) — 二維 DP 表的大小。
1. Initialize dp[m+1][n+1] with all zeros
2. For each string s in strs:
a. Count zeros and ones in s
b. For i from m down to zeros:
For j from n down to ones:
dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1)
3. Return dp[m][n]三維 DP(未壓縮):定義 dp[k][i][j] 為前 k 個字串中,使用最多 i 個 0 和 j 個 1 時的最大子集大小。轉移式相同,但顯式保留字串維度。時間 O(lmn),空間 O(lmn)。不如滾動陣列優化的二維版本。
記憶化搜索:遞迴定義 dfs(idx, remainM, remainN) = 從第 idx 個字串開始,剩餘容量為 (remainM, remainN) 時的最大子集大小。用 map 快取。時間相同但遞迴開銷較大,適合理解但不推薦提交。