LC474

题目链接

1.我们用递归还原状态转移

1.递归形式解决问题

class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { if(strs.size()==0 || (m==0 && n==0)) return 0; return tryfind(strs,strs.size()-1,m,n); } // 用m，n 拼出 strs[0,i] 的 最大个数 int tryfind(vector<string>& strs,int i,int m,int n){ if(i<0) return 0; int nums0=0; int nums1=0; string s = strs[i]; for(int i=0;i<s.size();i++){ //找出第i个字符0和1的个数 if(s[i]=='0') nums0++; else nums1++; } if(m>=nums0 && n>=nums1){ //如果剩下的0和1还够的话进行比较 是加上这个字符还是不加上大 return max(tryfind(strs,i-1,m,n), 1+tryfind(strs,i-1,m-nums0,n-nums1) ); }else{//mn不够的话就直接进行到下一个 return tryfind(strs,i-1,m,n); } } };

 

很明显 return max(tryfind(strs,i-1,m,n),1+tryfind(strs,i-1,m-nums0,n-nums1)) 这就会出现重叠子问题

例如：

f(8,5,4) = max(f(7,5,4),f(7,3,2)) str = 1100 f(8,5,2) = max(f(7,5,2),f(7,3,2)) str = 11 f(7,3,2) 会被重复计算

 

2.进行添加记忆化搜索代码 （自顶向下）

class Solution { public: int a[601][101][101]; //设置记忆化数组 int findMaxForm(vector<string>& strs, int m, int n) { if(strs.size()==0 || (m==0 && n==0)) return 0; memset(a,-1,sizeof(a)); return tryfind(strs,strs.size()-1,m,n); } int tryfind(vector<string>& strs,int i,int m,int n){ if(i<0) return 0; if(a[i][m][n]!=-1) //如果是之前记录过的函数 我们就直接取为之前记录的值 return a[i][m][n]; int nums0=0; int nums1=0; string s = strs[i]; for(int i=0;i<s.size();i++){ //找出第i个字符0和1的个数 if(s[i]=='0') nums0++; else nums1++; } if(m>=nums0 && n>=nums1){ //对于没有记录的值我们就正常计算 a[i][m][n] = max(tryfind(strs,i-1,m,n), 1+tryfind(strs,i-1,m-nums0,n-nums1) ); }else{//mn不够的话就直接进行到下一个 a[i][m][n] = tryfind(strs,i-1,m,n); } return a[i][m][n]; } };

虽然执行成功，但是时间很长和空间占用很大，分析其原因有二

递归方法栈过长导致执行时长增加三维数组在索引上的耗时和空间上的占用

3.非递归动态规划（为了解决上述的问题一我们可以使用循环来代替递归

class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { if(strs.size()==0 ||(m==0 && n==0)) return 0; int dp[601][101][101]; dp[i][j][k] 表示j个0，k个1组成s[0...i]的最大个数，默认0 for(int i=0;i<strs.size();i++){ int num0=0; int num1=0; string s=strs[i]; for(int j = 0;j<s.length();j++){ if(s[j] == '0'){ num0++; }else{ num1++; } } for(int j=m;j>=0;j--){ for(int k=n;k>=0;k--){ if(j>=num0 && k>=num1){ if(i==0){ dp[i][j][k]=1; }else{ dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-num0][k-num1]+1); } }else{ dp[i][j][k] = i>0 ? dp[i-1][j][k] : 0; } } } } return dp[strs.size()-1][m][n]; } };

4.

动态规划的空间优化

观察动态转移方程，我们发现dp[i][][] 只和dp[i-1][][] 有关，所以可以去掉第一维，只用一个二维数组保存上一次计算的结果

class Solution { public int findMaxForm(String[] strs, int m, int n) { if(strs.length == 0 || (m==0 && n==0)){ return 0; } int[][] dp = new int[m+1][n+1]; for(int i=0;i<strs.length;i++){ int numsOf0 = 0; int numsOf1 = 0; String str = strs[i]; for(int j = 0;j<str.length();j++){ if(str.charAt(j) == '0'){ numsOf0++; }else{ numsOf1++; } } for(int j=m;j>=numsOf0;j--){ for(int k=n;k>=numsOf1;k--){ dp[j][k] = Math.max(dp[j][k],1+dp[j-numsOf0][k-numsOf1]); } } } return dp[m][n]; }}

 

 

Ref:

作者：meetce- 链接：https://leetcode-cn.com/problems/ones-and-zeroes/solution/zi-ding-xiang-xia-ji-yi-sou-suo-zi-di-xiang-shang-/