有两个经典问题:一个是最长公共子序列(不连续)、最长公共子串(连续);
思路都是动态规划,直接上代码:
1 class Solution { 2 public: 3 4 int longestCommonSubsequence(string text1, string text2) { 5 int length1 = text1.length(); 6 int length2 = text2.length(); 7 8 int res = 0; 9 vector<vector<int>> dp(length1,vector<int>(length2,0)); 10 //dp[i][j] 表示 到A的第i个字符,到B的第j个字符 的最长公共子序列长度;i,j都是0为基; 11 for(int i = 0; i<length1;i++){ 12 for(int j = 0; j<length2; j++){ 13 char a = text1[i]; 14 char b = text2[j]; 15 if(i==0 || j==0){ 16 if(a==b){ 17 dp[i][j] = 1; 18 } 19 else if(j!=0){ 20 dp[i][j] = dp[0][j-1]; 21 } 22 else if(i!=0){ 23 dp[i][j] = dp[i-1][0]; 24 } 25 if(res<dp[i][j]){ 26 res = dp[i][j]; 27 } 28 continue; 29 } 30 if(a==b){ 31 dp[i][j] = dp[i-1][j-1]+1; 32 } 33 else{ 34 dp[i][j] = max(dp[i][j-1],dp[i-1][j]); 35 } 36 if(res<dp[i][j]){ 37 res = dp[i][j]; 38 } 39 } 40 } 41 return res; 42 43 } 44 };
原文:https://www.cnblogs.com/grooovvve/p/12371272.html