前言
到了三维整个难度就陡然上去了……
一、一和零
class Solution {
public:int zeros,ones;void count(string s){zeros=ones=0;for(int i=0;i<s.length();i++){if(s[i]=='0'){zeros++;}else{ones++;}}}int findMaxForm(vector<string>& strs, int m, int n) {//return recursion(0,m,n,strs);//vector<vector<vector<int>>>dp//(strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,-1)));//return memorized_search(0,m,n,strs,dp);//return DP(m,n,strs);return optimized_dp(m,n,strs);}//递归 -> 超时int recursion(int i,int z,int o,vector<string>&strs){if(i==strs.size()){return 0;}int p1=recursion(i+1,z,o,strs);//不要当前字符串int p2=0;//要count(strs[i]);if(zeros<=z&&ones<=o){p2=1+recursion(i+1,z-zeros,o-ones,strs);}return max(p1,p2);}//记忆化搜索int memorized_search(int i,int z,int o,vector<string>&strs,vector<vector<vector<int>>>&dp){if(i==strs.size()){return 0;}if(dp[i][z][o]!=-1){return dp[i][z][o];}int p1=memorized_search(i+1,z,o,strs,dp);int p2=0;count(strs[i]);if(zeros<=z&&ones<=o){p2=1+memorized_search(i+1,z-zeros,o-ones,strs,dp);}dp[i][z][o]=max(p1,p2);return dp[i][z][o];}//动态规划int DP(int m,int n,vector<string>&strs){vector<vector<vector<int>>>dp(strs.size()+1,vector<vector<int>>(m+1,vector<int>(n+1)));for(int i=strs.size()-1;i>=0;i--){for(int j=0;j<=m;j++){for(int k=0;k<=n;k++){int p1=dp[i+1][j][k];int p2=0;count(strs[i]);if(zeros<=j&&ones<=k){p2=1+dp[i+1][j-zeros][k-ones];}dp[i][j][k]=max(p1,p2);}}}return dp[0][m][n];}//空间压缩int optimized_dp(int m,int n,vector<string>&strs){vector<vector<int>>dp(m+1,vector<int>(n+1));
