問題來源

此題來源于LeetCode 474. Ones and Zeroes
在寫這篇之前，我百度了一下這道題，發現已經有很多人寫過這個問題了，然而大多數只是為了答題而答題，給出了代碼，很少有文字解釋的，也很少有深入拓展的。因此，我這次來給出一個比較詳盡的版本，并且在最后對結果進行了拓展。

問題簡介

已知一個字符串數組，數組內的字符串都是僅由0和1組成的，現在給定m個0和n個1，試問這m個0和n個1最多可以組成幾個數組中的字符串。
比如：

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3 Output: 4Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

又比如：

Input: Array = {"10", "0", "1"}, m = 1, n = 1 Output: 2Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

解決方案

這是一個非常典型的二維0/1背包問題，相當于是在問我們有一個背包的空間大小為m，最大載重為n，給定k個物品，已知每個物品的大小和重量，試問最多能放進多少個物品（每個物品只能放一次）。
該問題的狀態方程為

$$f(m,n,k)=max(f(m,n,k?1),1+f(m?i,n?j,k?1))$$

$f(m,n,k)$是指在限制為$(m,n)$的情況下，考慮前$k$個字符串所能得到的最多字符串的個數。
這個式子的意思是，我們從放第1個字符串開始考慮，直到第k個字符串，如果在限制為$(m,n)$的情況下，放這個字符串進去比不放這個字符串得到的個數要多，那么我們就放這個字符串進去，否則不放。
如果想直接看動態規劃在這里最簡潔的解法，請直接跳到解法3，有耐心的話就一步步看下去吧。

解法1

時間復雜度：$O(m?n?k)$
空間復雜度：$O(m?n?k)$
其中，$m$為0的個數， $n$為1的個數，$k$為已知字符串數組的長度strs.size()
這種解法雖然很浪費空間，但是保存了每種情況的狀態，只有在這種情況下，我們才能逆推出這個最大長度是由哪些字符串組成的。

class Solution { private:vector<vector<vector<int>>> rec;int strsN;private://計算每個字符串有幾個0和幾個1pair<int, int> countNums(string s){int os = 0;int zs = 0;for (int i = 0; i < s.length(); i++){if ('0' == s[i])zs++;}os = s.length() - zs;return make_pair(zs, os);}public:int findMaxForm(vector<string>& strs, int m, int n) {strsN = strs.size();//創建一個m*n*strN的數組來存放每種情況下的狀態rec = vector<vector<vector<int>>>(m + 1, vector<vector<int>>(n + 1, vector<int>(strsN, 0)));for (int count = 0; count < strsN; count++){pair<int, int> p = countNums(strs[count]);for (int i = m; i >= 0; i--){for (int j = n; j >= 0; j--){if (i >= p.first && j >= p.second)rec[i][j][count] = (count == 0 ? 1 : max(rec[i][j][count - 1], 1 + rec[i - p.first][j - p.second][count - 1]));elserec[i][j][count] = (count == 0 ? 0 : rec[i][j][count - 1]);}}}return rec[m][n][strsN - 1];} };

解法2

時間復雜度：$O(m?n?k)$
空間復雜度：$O(m?n?2)$，即$O(m?n)$
其中，$m$為0的個數， $n$為1的個數，$k$為已知字符串數組的長度strs.size()
然后，我們發現其實每次更新狀態$k$時僅僅用到了上一次的狀態$k?1$，所以我們可以將存儲狀態的數組降成$m?n?2$的大小。

class Solution { private:vector<vector<vector<int>>> rec;private://計算每個字符串有幾個0和幾個1pair<int, int> countNums(string s){int os = 0;int zs = 0;for (int i = 0; i < s.length(); i++){if ('0' == s[i])zs++;}os = s.length() - zs;return make_pair(zs, os);}public:int findMaxForm(vector<string>& strs, int m, int n) {//創建一個m*n*2的數組來存放每種情況下的狀態rec = vector<vector<vector<int>>>(m + 1, vector<vector<int>>(n + 1, vector<int>(2, 0)));for (int count = 0; count < strs.size(); count++){pair<int, int> p = countNums(strs[count]);//設置level來讓rec[i][j][0]和rec[i][j][1]輪流變成上一組的狀態int level = count % 2;for (int i = m; i >= 0; i--){for (int j = n; j >= 0; j--){ if (i >= p.first && j >= p.second)if (0 == level)rec[i][j][0] = max(rec[i][j][1], 1 + rec[i - p.first][j - p.second][1]);elserec[i][j][1] = max(rec[i][j][0], 1 + rec[i - p.first][j - p.second][0]);elseif (0 == level)rec[i][j][0] = rec[i][j][1];elserec[i][j][1] = rec[i][j][0];}}}return max(rec[m][n][0], rec[m][n][1]);} };

解法3

時間復雜度：$O(m?n?k)$
空間復雜度：$O(m?n)$
其中，$m$為0的個數， $n$為1的個數，$k$為已知字符串數組的長度strs.size()
然后，我們又再次發現，其實我們把上一次的狀態和這次的狀態放在同一個數組中就可以了！因為更新時是從后往前的，要用到的上一次的值并沒有受到影響，于是又有了如下解法

class Solution { private:vector<vector<int>> rec;private://計算每個字符串有幾個0和幾個1pair<int, int> countNums(string s){int os = 0;int zs = 0;for (int i = 0; i < s.length(); i++){if ('0' == s[i])zs++;}os = s.length() - zs;return make_pair(zs, os);}public:int findMaxForm(vector<string>& strs, int m, int n) {//設置一個二維數組來記錄狀態rec = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));for (int count = 0; count < strs.size(); count++){pair<int, int> p = countNums(strs[count]);int level = count % 2;for (int i = m; i >= p.first; i--){for (int j = n; j >= p.second; j--){ rec[i][j] = max(rec[i][j], 1 + rec[i - p.first][j - p.second]);}}}return rec[m][n];} };

拓展——輸出某組解

如果僅僅是針對問題本身的話，解法3自然是最理想的一種解法。但是，如果我們想知道這個最大長度的字符串組是由哪些字符串組成的又該怎么辦呢？這個時候，就要用解法1記錄了所有狀態的數組逆推了~
下面給出的代碼只能找到其中的一組解，并不能找到所有解，因為可能有很多種情況。找所有解的方法只需在這之上拓展一下即可，不過不要忽略了重復解的情況，這是一個難點~

class Solution { private:vector<vector<vector<int>>> rec;int strsN;private:pair<int, int> countNums(string s){int os = 0;int zs = 0;for (int i = 0; i < s.length(); i++){if ('0' == s[i])zs++;}os = s.length() - zs;return make_pair(zs, os);}public:void findMaxForm(vector<string>& strs, int m, int n) {strsN = strs.size();rec = vector<vector<vector<int>>>(m + 1, vector<vector<int>>(n + 1, vector<int>(strsN, 0)));for (int count = 0; count < strsN; count++){pair<int, int> p = countNums(strs[count]);for (int i = m; i >= 0; i--){for (int j = n; j >= 0; j--){if (i >= p.first && j >= p.second)rec[i][j][count] = (count == 0 ? 1 : max(rec[i][j][count - 1], 1 + rec[i - p.first][j - p.second][count - 1]));elserec[i][j][count] = (count == 0 ? 0 : rec[i][j][count - 1]);}}}}vector<string> getOneSol(vector<string> strs, int m, int n){//調用findMaxForm()把狀態存到rec中findMaxForm(strs, m, n);vector<string> res;int zs = m;int os = n;for (int i = strsN - 1; i >= 1; i--){pair<int, int> p = countNums(strs[i]);if (rec[zs][os][i] == rec[zs][os][i - 1])continue;else{res.push_back(strs[i]);zs -= p.first;os -= p.second;}if (zs <= 0 && os <= 0)break;}pair<int, int> p = countNums(strs[0]);if (p.first <= zs && p.second <= os)res.push_back(strs[0]);return res;} };

結束語

很多動態規劃的問題都可以演變成背包問題，因此掌握背包問題的本質是非常重要的。
如有不足，還請指正~

總結

以上是生活随笔為你收集整理的LeetCode 474. Ones and Zeroes 动态规划解法+拓展的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。