最长公共子序列(LCS)的刷题记录

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m &＃61; text1.size(),n&＃61;text2.size();//定义&＃xff1a;对于s1[0..i-1]和s2[0..j-1],它们的lcs长度是dp[i][j]vector<vector<int>>dp(m&＃43;1,vector<int>(n&＃43;1,0));//base case:dp[0][...] &＃61; dp[...][0] &＃61; 0,已初始化for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){//状态转移逻辑if(text1[i-1]&＃61;&＃61;text2[j-1]){dp[i][j] &＃61; dp[i-1][j-1]&＃43;1;}else{dp[i][j] &＃61; max(dp[i][j-1],dp[i-1][j]);}}}return dp[m][n];}
};
自顶向下的dp&＃xff1a;

class Solution {
public:
int memo[1000][1000];int longestCommonSubsequence(string text1, string text2) {init(memo);return dp(text1,text2,text1.size()-1,text2.size()-1);}//dp[i][j]的含义tex1[..i]和tex2[..j]之间的LCS
private://备忘录&＃xff0c;由于存在重复子问题&＃xff0c;需通过备忘录提高效率void init(int (*memo)[1000]){memset(memo,0,sizeof(memo));}int dp(string& text1,string& text2,int i,int j){//base case:if(i&＃61;&＃61;-1||j&＃61;&＃61;-1)return 0;if(memo[i][j]!&＃61;0)return memo[i][j];
//自顶向下&＃xff0c;若相等则说明该字符存在于LCS中(&＃43;1)&＃xff0c;那么dp[i][j]等于dp[i-1][j-1]的LCS&＃43;1&＃xff0c;if(text1[i] &＃61;&＃61; text2[j])return memo[i][j]&＃61;dp(text1,text2,i-1,j-1)&＃43;1;
//其余情况就判断单个字符是否存在于LCS中(通过看dp[i][j-1]和dp[i-1][j])&＃xff0c;取LCS最大的那个情况else{return memo[i][j]&＃61;max(dp(text1,text2,i-1,j),dp(text1,text2,i,j-1));}}
};