这道应该是三道题中最难的，因为之前在leetcode上做过最长回文字串，典型的动态规划 回文问题动态规划的关键在于，只要中间部分是回文，并且两边相等，那么也会构成回文，这样就可以基于前一状态获得当前状态了！ 难点在于写出构造方程（废话。。），在于当左右指针不等的时候如何推出结果！
#include<string> #include<iostream> #include<vector> using namespace std; int Solution(string s){ int length = s.size(); vector<vector<int>> dp(length,vector<int>(length,0)); for(int l=0;l<length;l++){ for(int i=0;i+l<length;i++){ int j = i+l; if(l<=1){ if(s[i] != s[j]) dp[i][j] = 1; } else{ if(s[i]!=s[j]){ //难点所在！！ dp[i][j] = min(dp[i][j-1],dp[i+1][j]) + 1; } else dp[i][j] = dp[i+1][j-1]; } } } return dp[0][length-1]; } int main(){ string s; while(cin>>s){ cout<<Solution(s)<<endl; } return 0; }看其他人的`题解还有一种方法是，将字符串逆序，然后计算两者的“最大公共子序列”，注意了，子序列是不需要连续的，而子串是需要连续的！ 单独把“最大公共子序列”列出来： 这题的dp构造比较奇特，我用dp[i][j]表示：对于string1，从0～i，和对于string2，从0～j，两部分之间的最大公共子序列的长度！ 那么，得出状态转移方程：
当str1[i] == str2[j]的时候，dp[i][j] = dp[i-1][j-1] + 1; 当str1[i] != str2[j]的时候，dp[i][j] = max(dp[i][j-1],dp[i-1][j])，这是题目的关键 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int length1 = text1.size(); int length2 = text2.size(); vector<vector<int>> dp(length1,vector<int>(length2,0)); if(text1[0] == text2[0]) dp[0][0] = 1; for(int i=1;i<length1;i++){ if(text2[0] == text1[i]) dp[i][0] = 1; else dp[i][0] = dp[i-1][0]; } for(int j=1;j<length2;j++){ if(text1[0] == text2[j]) dp[0][j] = 1; else dp[0][j] = dp[0][j-1]; } for(int i=1;i<length1;i++){ for(int j=1;j<length2;j++){ if(text1[i]!=text2[j]) //这题的重点！！ dp[i][j] = max(dp[i][j-1],dp[i-1][j]); else dp[i][j] = dp[i-1][j-1] + 1; } } return dp[length1-1][length2-1]; } };