通知：我已經將刷題指南全部整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在電腦上閱讀，這個倉庫每天都會更新，大家快去給一個star支援一下吧！
474.一和零給你一個二進位制字串陣列 strs 和兩個整數 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 <= 6001 <= strs[i].length <= 100strs[i] 僅由 '0' 和 '1' 組成1 <= m, n <= 100思路這道題目，還是比較難的，也有點像程式設計師自己給自己出個腦筋急轉彎，程式設計師何苦為難程式設計師呢哈哈。
來說題，本題不少同學會認為是多重揹包，一些題解也是這麼寫的。
其實本題並不是多重揹包，再來看一下這個圖，捋清幾種揹包的關係
多重揹包是每個物品，數量不同的情況。
本題中strs 數組裡的元素就是物品，每個物品都是一個！
而m 和 n相當於是一個揹包，兩個維度的揹包。
理解成多重揹包的同學主要是把m和n混淆為物品了，感覺這是不同數量的物品，所以以為是多重揹包。
但本題其實是01揹包問題！
這不過這個揹包有兩個維度，一個是m 一個是n，而不同長度的字串就是不同大小的待裝物品。
開始動規五部曲：
確定dp陣列（dp table）以及下標的含義dp[i][j]：最多有i個0和j個1的strs的最大子集的大小為dp[i][j]。
確定遞推公式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]);
對比一下就會發現，字串的zeroNum和oneNum相當於物品的重量（weight[i]），字串本身的個數相當於物品的價值（value[i]）。
這就是一個典型的01揹包！ 只不過物品的重量有了兩個維度而已。
dp陣列如何初始化在動態規劃：關於01揹包問題，你該瞭解這些！（滾動陣列）中已經講解了，01揹包的dp陣列初始化為0就可以。
因為物品價值不會是負數，初始為0，保證遞推的時候dp[i][j]不會被初始值覆蓋。
確定遍歷順序在動態規劃：關於01揹包問題，你該瞭解這些！（滾動陣列）中，我們講到了01揹包為什麼一定是外層for迴圈遍歷物品，內層for迴圈遍歷揹包容量且從後向前遍歷！
那麼本題也是，物品就是strs裡的字串，揹包容量就是題目描述中的m和n。
程式碼如下：
for (string str : strs) { // 遍歷物品 int oneNum = 0, zeroNum = 0; for (char c : str) { if (c == '0') zeroNum++; else oneNum++; } for (int i = m; i >= zeroNum; i--) { // 遍歷揹包容量且從後向前遍歷！ for (int j = n; j >= oneNum; j--) { dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); } }}有同學可能想，那個遍歷揹包容量的兩層for迴圈先後循序有沒有什麼講究？
沒講究，都是物品重量的一個維度，先遍歷那個都行！
舉例推導dp陣列以輸入：["10","0001","111001","1","0"]，m = 3，n = 3為例
最後dp陣列的狀態如下所示：
以上動規五部曲分析完畢，C++程式碼如下：
class Solution {public: int findMaxForm(vector<string>& strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 預設初始化0 for (string str : strs) { // 遍歷物品 int oneNum = 0, zeroNum = 0; for (char c : str) { if (c == '0') zeroNum++; else oneNum++; } for (int i = m; i >= zeroNum; i--) { // 遍歷揹包容量且從後向前遍歷！ for (int j = n; j >= oneNum; j--) { dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); } } } return dp[m][n]; }};不少同學刷過這道提，可能沒有總結這究竟是什麼揹包。
這道題的本質是有兩個維度的01揹包，如果大家認識到這一點，對這道題的理解就比較深入了。
力扣刷題指南：https://github.com/youngyangyang04/leetcode-master
這裡每天8:35準時推送一道經典演算法題目，我選擇的每道題目都不是孤立的，而是由淺入深，環環相扣，幫你梳理演算法知識脈絡，輕鬆學演算法！