[数据结构与算法]最长回文子序列的两种解法（动态规划和反转字符串）

1 题目链接

LeetCode

2 动态规划

这个主要是用dp二维数组来解，应该是用的最多的方法了，这里就不再写了，有兴趣可以去看题解。
题解

3 反转字符串法

这里是利用回文数的特征：正着读和反着读都是一样的，就可以把原有的字符串str1反转变成一个新的str2，然后求出这两个子序列的最长公共子序列数即可，这里就把问题转换为了最长公共子序列问题。
例如：

最长公共子序列的题目为：
最长公共子序列
关于这道题LeetCode里面有详细的解答，这里就不写解答和代码了。

反转字符串法代码

Java:

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        //将s反转，得到另一个字符串
        String t = new StringBuffer(s).reverse().toString();
         //最后就可以用最长公共子序列来做了
        int[][] dp = new int[n+1][n+1];
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
       return dp[n][n];
    }
}

C++

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        //将s反转，得到另一个字符串
        string t = s;
        reverse(t.begin(),t.end());

         //最后就可以用最长公共子序列来做了
       vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(s[i-1]==t[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
       return dp[n][n];
    }
};