力扣动态规划中等题困难题+字符串DP专题20210807
总结：
二叉树的DP，采用哈希表map进行存储。自底向上类似后序遍历。
搜索有DFS和BFS，可以理解为，DFS搜索是递归的子集。
一维数组存储可以替换为两个变量或者滚动数组（如果可以的话）。
vector的二维数组申请以及初始化：
1 vector<vector<int>> dp(n+1,vector<int>(3,0));
vector二维数组的行列大小定义：
1 int maximalSquare(vector<vector<char>>& matrix) { 2 int m=matrix.size(); 3 int m=matrix[0].size(); 4 }
总结：回溯，就是试探性穷举，不成功就退回到上一个状态，继续尝试下一个分支。
力扣 的 139题 一个字符串是否可以在字典集合里完全找到
方法一：采用回溯
代码如下：
1 class Solution { 2 private: 3 //回溯思想，时间复杂度o(2^n)，空间复杂度O(n)。 4 bool backs(string& s, unordered_set<string>& wordSet,vector<int>& memo,int startindex) 5 { 6 if(startindex==s.size()) 7 { 8 return true; 9 } 10 if(memo[startindex]!=-1) 11 { 12 return memo[startindex]; 13 } 14 for(int i=startindex;i<s.size();i++) 15 { 16 string word = s.substr(startindex,i-startindex+1); 17 18 if(wordSet.find(word)!=wordSet.end()&& backs(s,wordSet,memo,i+1)) 19 { 20 memo[i]=1; 21 return true; 22 } 23 24 } 25 memo[startindex]=0; 26 return false; 27 } 28 29 public: 30 bool wordBreak(string s, vector<string>& wordDict) { 31 unordered_set<string> wordSet(wordDict.begin(),wordDict.end()); 32 vector<int> memo(s.size(),-1);//设计一个备忘录，存储重复子问题，比如ab和ab，在第二次扫描到ab的时候，可以直接调用值，而不需要重新计算。 33 return backs(s,wordSet,memo,0); 34 } 35 };
参考链接：https://leetcode-cn.com/problems/word-break/solution/dai-ma-sui-xiang-lu-139-dan-ci-chai-fen-50a1a/
方法二：动态规划
类似01背包问题，
01背包问题模板
代码如下：
1 class Solution { 2 3 public: 4 //采用动态规划的思想 5 bool wordBreak(string s, vector<string>& wordDict) { 6 unordered_set<string> wordSet(wordDict.begin(),wordDict.end()); 7 vector<bool> dp(s.size()+1,false); // dp[i]表示长度为i的时候，可拆分成1个或者多个在wordSet（字典集合） 里面的单词 8 dp[0]=true; 9 for(int i=1;i<=s.size();i++)//这是遍历字符串，相当于物品 10 { 11 for(int j=0;j<i;j++)//这个是单词，相当于背包 12 { 13 string word = s.substr(j,i-j); 14 if((wordSet.find(word) != wordSet.end()) && dp[j]) 15 { 16 dp[i]=true; 17 } 18 } 19 } 20 return dp[s.size()]; 21 } 22 };
力扣 279题 完全平方数
采用动态规划的思想
代码如下：
1 class Solution { 2 public: 3 int numSquares(int n) { 4 //动态规划的思想 5 vector<int> dp(n+1); 6 dp[0]=0;//dp[0]需要初始化为0 7 8 for(int i=1;i<=n;i++) 9 { 10 int m = INT_MAX; 11 for(int j=1;j*j<=i;j++) 12 { 13 m = min(m,dp[i-j*j]); //m表示已有一个平方数的基础上，需要的最少数量 14 dp[i]=1+m; // 15 } 16 } 17 return dp[n]; 18 } 19 };
力扣583题 两个字符串的删除
两个字符串的最长公共子串模板：
定义：
dp[i][j]表示以i,j结尾的最长公共子串。
转移公式：
dp[i][j]= （dp[i]==dp[j] ? (dp[i-1][j-1]+1) ：0）
C++代码模板：
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<cstdio> 5 using namespace std; 6 7 char s1[1000],s2[1000]; 8 int dp[1000][1000]; 9 int main() 10 { 11 while (~scanf("%s %s",s1+1,s2+1)) 12 { 13 int len1 = strlen(s1+1); 14 int len2 = strlen(s2+1); 15 int ans = 0; 16 for (int i = 1;i <= len1; i++) 17 for (int j = 1;j <= len2; j++) 18 { 19 if (s1[i] == s2[j]) 20 { 21 dp[i][j] = dp[i-1][j-1]+1; 22 ans = max(ans,dp[i][j]); 23 } 24 25 } 26 printf("%d ",ans); 27 memset(dp,0,sizeof(dp)); 28 memset(s1,0,sizeof(s1)); 29 memset(s2,0,sizeof(s2)); 30 } 31 }
Java代码模板：
1 public static int lcs(String str1, String str2) { 2 int len1 = str1.length(); 3 int len2 = str2.length(); 4 int result = 0; //记录最长公共子串长度 5 int c[][] = new int[len1+1][len2+1]; 6 for (int i = 0; i <= len1; i++) { 7 for( int j = 0; j <= len2; j++) { 8 if(i == 0 || j == 0) { 9 c[i][j] = 0; 10 } else if (str1.charAt(i-1) == str2.charAt(j-1)) { 11 c[i][j] = c[i-1][j-1] + 1; 12 result = max(c[i][j], result); 13 } else { 14 c[i][j] = 0; 15 } 16 } 17 } 18 return result; 19 }
参考链接：https://www.iamivan.net/a/MNv05oM.html
滚动优化：主要是考虑到两个状态可以滚动
C++代码如下：
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<cstdio> 5 using namespace std; 6 7 char s1[1000],s2[1000]; 8 int dp[2][1000]; 9 int main() 10 { 11 while (~scanf("%s %s",s1+1,s2+1)) 12 { 13 int len1 = strlen(s1+1); 14 int len2 = strlen(s2+1); 15 int ans = 0, cur = 0; 16 for (int i = 1;i <= len1; i++) 17 { 18 cur ^= 1; 19 for (int j = 1;j <= len2; j++) 20 { 21 if (s1[i] == s2[j]) 22 { 23 dp[cur][j] = dp[cur^1][j-1]+1; 24 ans = max(ans,dp[cur][j]); 25 } 26 else dp[cur][j] = 0; 27 28 } 29 } 30 31 printf("%d ",ans); 32 memset(dp,0,sizeof(dp)); 33 memset(s1,0,sizeof(s1)); 34 memset(s2,0,sizeof(s2)); 35 } 36 }
参考链接：https://blog.csdn.net/sugarbliss/article/details/80731688
题目代码：
1 class Solution { 2 public: 3 int minDistance(string word1, string word2) { 4 //动态规划的思想 5 int a = word1.size(); 6 int b = word2.size(); 7 vector<vector<int>> dp(a+1,vector<int>(b+1,0)); 8 int ans = 0; 9 int res=0; 10 for(int i=1;i<=a;i++) 11 { 12 for(int j=1;j<=b;j++) 13 { 14 15 if(word1[i-1]==word2[j-1]) 16 { 17 dp[i][j]= dp[i-1][j-1]+1; 18 ans = max(ans,dp[i][j]); 19 } 20 else 21 { 22 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//当i,j不相等时，dp[i][j]等于前一个状态的值，max(dp[i-1][j],dp[i][j-1]) 23 } 24 } 25 } 26 res = (a+b-(2*dp[a][b])); 27 //cout<<res<<endl; 28 return res; 29 } 30 };
参考链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-8cai1/
力扣 678题 有效的括号字符串
方法一：采用两个栈
代码如下：
1 class Solution { 2 public: 3 bool checkValidString(string s) { 4 //设两个栈，一个存左括号，一个存星号，遇右括号，先匹配左括号组，再匹配星号组，都没有返回false 5 //匹配完剩余星号和左括号匹配，注意左括号要在星号左侧，左括号不能有剩余 6 stack<int> left,star; 7 8 for(int i=0;i<s.size();i++)//把（ 和 * 放进两个两个栈里面，遇到 ），就先判断（的栈有的话，就抛出一个；如果（的栈没有，就抛出*的栈里面的一个；都为空，就返回false。 9 { 10 if(s[i]=='(') 11 { 12 left.push(i); 13 } 14 else if(s[i]=='*') 15 { 16 star.push(i); 17 } 18 else 19 { 20 if(left.empty() && star.empty()) 21 { 22 return false; 23 } 24 if(!left.empty()) 25 { 26 left.pop(); 27 } 28 else 29 star.pop(); 30 } 31 } 32 while(!left.empty() && !star.empty())//判断左括号和* 可能还没完全消除的情况，如果左括号在*的右边，就是返回false，因为*变成三种方式的任何一种，都不是有效字符串。 33 { 34 if(left.top()>star.top())//这是*(的情况，不是有效字符串 35 { 36 return false; 37 } 38 left.pop(); 39 star.pop(); 40 } 41 return left.empty(); 42 } 43 };
方法二：两个变量的方法
代码如下：
1 class Solution { 2 public: 3 bool checkValidString(string s) { 4 //两个变量的方法 5 //对未匹配的左括号设置一个变化的范围，用两个变量分别表示范围的最小值和最大值。一般的括号匹配都是左括号设置一个栈，有右括号，则左括号出栈。可以不用栈，用一个变量表示未匹配的左括号即可。 本题加了*，则需要两个变量表示未匹配的左括号的数量 6 int min=0; 7 int max=0; 8 int n=s.size(); 9 for(int i=0;i<n;i++) 10 { 11 if(s[i]=='(')//左括号的时候，最小值加一，最大值也是加一 12 { 13 min++; 14 high++; 15 } 16 else if(s[i]==')')//右括号的时候，最小值是0和减一的最大值，最大值是肯定减一的 17 { 18 min = max(0,min-1); 19 high--; 20 } 21 else{ //当出现*的时候，最小值*看成右括号，是0和减一的最大值，最大值是*看成左括号，最大值加一 22 min = max(0,min-1); 23 high++; 24 } 25 26 } 27 return min<=0; //当未匹配的左括号的数量小于等于0的时候才是返回true，否则返回false 28 29 } 30 }; 31 32 33 /**class Solution { 34 public: 35 bool checkValidString(string s) { 36 //设两个栈，一个存左括号，一个存星号，遇右括号，先匹配左括号组，再匹配星号组，都没有返回false 37 //匹配完剩余星号和左括号匹配，注意左括号要在星号左侧，左括号不能有剩余 38 stack<int> left,star; 39 40 for(int i=0;i<s.size();i++)//把（ 和 * 放进两个两个栈里面，遇到 ），就先判断（的栈有的话，就抛出一个；如果（的栈没有，就抛出*的栈里面的一个；都为空，就返回false。 41 { 42 if(s[i]=='(') 43 { 44 left.push(i); 45 } 46 else if(s[i]=='*') 47 { 48 star.push(i); 49 } 50 else 51 { 52 if(left.empty() && star.empty()) 53 { 54 return false; 55 } 56 if(!left.empty()) 57 { 58 left.pop(); 59 } 60 else 61 star.pop(); 62 } 63 } 64 while(!left.empty() && !star.empty())//判断左括号和* 可能还没完全消除的情况，如果左括号在*的右边，就是返回false，因为*变成三种方式的任何一种，都不是有效字符串。 65 { 66 if(left.top()>star.top())//这是*(的情况，不是有效字符串 67 { 68 return false; 69 } 70 left.pop(); 71 star.pop(); 72 } 73 return left.empty(); 74 } 75 };**/
方法三：从前往后和从后往前，两次遍历的方法
代码如下：
1 class Solution { 2 public: 3 bool checkValidString(string s) { 4 //两次遍历的方法 5 int n = s.size(); 6 int left = 0;//左括号数量 7 int right = 0;//右括号数量 8 int star = 0;//*的数量 9 for(int i=0;i<n;i++)//从前往后遍历，遇到）的时候，先删除（，没有（就删除* 10 { 11 if(s[i]=='(') 12 { 13 left++; 14 } 15 else if(s[i]=='*') 16 { 17 star++; 18 } 19 else 20 { 21 if(left>0) 22 { 23 left--; 24 } 25 else if(star>0) 26 { 27 star--; 28 } 29 else return false; 30 } 31 } 32 star = 0; 33 for(int i=n-1;i>=0;i--)//从后往前遍历，遇到（的时候，先删），没有）就删除* 34 { 35 if(s[i]=='*') 36 { 37 star++; 38 } 39 else if(s[i]==')') 40 { 41 right++; 42 } 43 else 44 { 45 if(right>0) right--; 46 else if(star>0) star--; 47 else 48 { 49 return false;//此时左括号没有，所以返回false 50 } 51 } 52 53 } 54 return true; 55 } 56 };
方法四：回溯
代码如下：
1 class Solution { 2 private: 3 bool check(string& s,int start,int count)//有开始点的下标位置，有count记录未匹配的左括号的数量 4 5 { 6 if(count<0) 7 { 8 return false; 9 } 10 for(int i=start;i<s.size();i++) 11 { 12 if(s[i]=='(') 13 { 14 count++; 15 } 16 else if(s[i]==')') 17 { 18 if(count==0) 19 { 20 return false; 21 } 22 count--; 23 } 24 else if(s[i]=='*') 25 { 26 return check(s,i+1,count) || check(s,i+1,count+1) || check(s,i+1,count-1); 27 } 28 } 29 return count==0; 30 } 31 32 33 public: 34 bool checkValidString(string s) { 35 //DFS，回溯的方法 36 return check(s,0,0); 37 } 38 };
以上代码会超时，可以用map或者vector存储start和count的值，达到优化效果，感兴趣可以试一试。
参考链接：https://leetcode-cn.com/problems/valid-parenthesis-string/solution/fen-zhi-tan-xin-shuang-xiang-bian-li-shuang-zhan-j/
926. 将字符串翻转到单调递增
采用动态规划思想，
代码如下：
1 class Solution { 2 public: 3 int minFlipsMonoIncr(string s) { 4 //动态规划思想 5 int n = s.size(); 6 vector<int> dp(n+1); 7 dp[n] = 0;//dp[i]表示下标是i的时候，i~n-1之间1的数量 8 9 for(int i=n-1;i>=0;i--) 10 { 11 if(s[i]=='1') 12 { 13 dp[i]=dp[i+1]+1; 14 } 15 else 16 { 17 dp[i]=dp[i+1]; 18 } 19 // cout<<i<<" "<<dp[i]<<endl; 20 } 21 22 int r = INT_MAX; 23 for(int i=1;i<n;i++) 24 { 25 r = min(r,dp[0]-dp[i]+n-i-dp[i]);//dp[0]-dp[i]表示0~i-1之间1的数量,n-i-dp[i]表示i+1~n-1之间的0的数量。两者的和就是需要修改的数量 26 // cout<<r<<" "<<dp[0]-dp[i]+n-i-dp[i]<<endl; 27 } 28 int count=0; 29 for(int i=0;i<n;i++) 30 { 31 if(s[i]=='1') 32 { 33 count++; 34 } 35 } 36 if(count<r || (n-count)<r)//修改成全0或者全1的情况，需要的次数，小于之前的修改次数的时候，可以取最小值，并返回这个最小值 37 { 38 return min(count,n-count); 39 } 40 return r; 41 } 42 };
背包问题刷题指南：
参考链接：https://blog.csdn.net/youngyangyang04/article/details/114253921