问题：
给定一组只包含‘0‘ ‘1‘ 的字符串，给定两个正整数m和n，问，要使用m个‘0‘ n个‘1‘，能最多构成多少个给出字符串组中的字符串。
Example 1: Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3 Output: 4 Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0". Example 2: Input: strs = ["10","0","1"], m = 1, n = 1 Output: 2 Explanation: You could form "10", but then you‘d have nothing left. Better form "0" and "1". Constraints: 1 <= strs.length <= 600 1 <= strs[i].length <= 100 strs[i] consists only of digits ‘0‘ and ‘1‘. 1 <= m, n <= 100
解法：DP(动态规划) 0-1 knapsack problem（0-1背包问题）
1.确定【状态】：
2.确定【选择】：
3. dp[i][m][n]的含义：
前 i 个字符串中，用m个‘0‘ n个‘1‘ 最多能组成的字符串个数。
4. 状态转移：
dp[i][m][n]= OR {
}
5. base case：
代码参考：
1 class Solution { 2 public: 3 //dp[i][m][n]:in first i strs, the max number of strs can be formed by m 0s and n 1s. 4 //case_1.select strs[i] : = dp[i-1][m-strs[i].count(‘0‘)][n-strs[i].count(‘1‘)]+1 5 //case_2.not select strs[i]: = dp[i-1][m][n] 6 //dp[i][m][n] = max(case_1, case_2) 7 //base: dp[0][m][n]=0 8 //dp[i][0][0]=0 9 int findMaxForm(vector<string>& strs, int m, int n) { 10 vector<vector<vector<int>>> dp(strs.size()+1, vector<vector<int>>(m+1, vector<int>(n+1, 0))); 11 for(int i=1; i<=strs.size(); i++) { 12 int cout_1 = count(strs[i-1].begin(), strs[i-1].end(), ‘1‘); 13 int cout_0 = count(strs[i-1].begin(), strs[i-1].end(), ‘0‘); 14 for(int M=0; M<=m; M++) { 15 for(int N=0; N<=n; N++) { 16 if(M-cout_0>=0 && N-cout_1>=0) { 17 dp[i][M][N] = max(dp[i-1][M-cout_0][N-cout_1]+1, dp[i-1][M][N]); 18 } else { 19 dp[i][M][N] = dp[i-1][M][N]; 20 } 21 } 22 } 23 } 24 return dp[strs.size()][m][n]; 25 } 26 };
?? 优化：空间复杂度：3维->2维
去掉 i
将 m和n 倒序遍历。
理由参考：https://www.cnblogs.com/habibah-chang/p/13581649.html
代码参考：
1 class Solution { 2 public: 3 //dp[i][m][n]:in first i strs, the max number of strs can be formed by m 0s and n 1s. 4 //case_1.select strs[i] : = dp[i-1][m-strs[i].count(‘0‘)][n-strs[i].count(‘1‘)]+1 5 //case_2.not select strs[i]: = dp[i-1][m][n] 6 //dp[i][m][n] = max(case_1, case_2) 7 //base: dp[0][m][n]=0 8 //dp[i][0][0]=0 9 int findMaxForm(vector<string>& strs, int m, int n) { 10 vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); 11 for(int i=1; i<=strs.size(); i++) { 12 int cout_1 = count(strs[i-1].begin(), strs[i-1].end(), ‘1‘); 13 int cout_0 = count(strs[i-1].begin(), strs[i-1].end(), ‘0‘); 14 for(int M=m; M>=0; M--) { 15 for(int N=n; N>=0; N--) { 16 if(M-cout_0>=0 && N-cout_1>=0) { 17 dp[M][N] = max(dp[M-cout_0][N-cout_1]+1, dp[M][N]); 18 } 19 } 20 } 21 } 22 return dp[m][n]; 23 } 24 };
原文：https://www.cnblogs.com/habibah-chang/p/13582663.html