題目：

給你一個二進制字符串數(shù)組 strs 和兩個整數(shù) m 和 n 。

請你找出并返回 strs 的最大子集的長度，該子集中 最多 有 m 個 0 和 n 個 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

輸入：

strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3

輸出：

4

解釋：

最多有 5 個 0 和 3 個 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他滿足題意但較小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不滿足題意，因為它含 4個 1 ，大于 n 的值 3 。

示例 2：

輸入：

strs = [“10”, “0”, “1”], m = 1, n = 1

輸出：

2

解釋：

最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 僅由 ‘0’ 和’1’ 組成
• 1 <= m, n <= 100

思路：

本題是01背包問題

只不過這個背包有兩個維度，一個是m 一個是n，而不同長度的字符串就是不同大小的待裝物品。

動態(tài)規(guī)劃五部曲：

1. 確定dp數(shù)組（dp table）以及下標的含義

dp[i][j]：最多有i個0和j個1的strs的最大子集的大小為dp[i][j]。

2. 確定遞推公式

dp[i][j] 可以由前一個strs里的字符串推導出來，strs里的字符串有zeroNum個0，oneNum個1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我們在遍歷的過程中，取dp[i][j]的最大值。

所以遞推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此時大家可以回想一下01背包的遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

對比一下就會發(fā)現(xiàn)，字符串的zeroNum和oneNum相當于物品的重量（weight[i]），字符串本身的個數(shù)相當于物品的價值（value[i]）。

這就是一個典型的01背包！ 只不過物品的重量有了兩個維度而已。

dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)

3. dp數(shù)組如何初始化

01背包的dp數(shù)組初始化為0就可以。

因為物品價值不會是負數(shù)，初始為0，保證遞推的時候dp[i][j]不會被初始值覆蓋。

4. 確定遍歷順序

01背包一定是外層for循環(huán)遍歷物品，內(nèi)層for循環(huán)遍歷背包容量且從后向前遍歷！

那么本題也是，物品就是strs里的字符串，背包容量就是題目描述中的m和n。

代碼如下：

            # 遍歷m到zero_num，更新dp數(shù)組for i in range(m, zero_num - 1, -1):# 遍歷n到one_num，更新dp數(shù)組for j in range(n, one_num - 1, -1):# 更新dp[i][j]的值dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)

m 和 n都是物品重量的一個維度，先遍歷哪個都可以。

5. 舉例推導dp數(shù)組
   以輸入：[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3為例

最后dp數(shù)組的狀態(tài)如下所示：

代碼及詳細注釋：

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:# 創(chuàng)建一個二維數(shù)組dp，用于記錄可以由前i個字符串組成的最大子集的個數(shù)dp = [[0] * (n + 1) for _ in range(m + 1)]# 遍歷每個字符串for s in strs:zero_num = s.count('0')  # 統(tǒng)計0的個數(shù)one_num = s.count('1')  # 統(tǒng)計1的個數(shù)# 遍歷m到zero_num，更新dp數(shù)組for i in range(m, zero_num - 1, -1):# 遍歷n到one_num，更新dp數(shù)組for j in range(n, one_num - 1, -1):# 更新dp[i][j]的值dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)# 返回dp[m][n]，表示可以由給定數(shù)量的0和1組成的最大子集的個數(shù)return dp[m][n]

• 時間復雜度: O(kmn)，k 為strs的長度
• 空間復雜度: O(mn)