给定一个字符串str，求最长回文子序列长度。

问题描述：

        给定一个字符串str，求最长回文子序列长度。

思想：

思想一：

        根据回文串的性质，我们可以生成一个新的字符串，新字符串的顺序是原来字符串的倒序。本题可以转化为两个字符串求最长的公共子序列。

        使用动态规划的思想。定义二维数组dp，行表示原本的字符串str1的字符，列表示翻转后字符串str2的每一个字符。二维数组dp[i][j]的含义是：字符串str1从下标0~i和字符串str2从下标0~j的最长公共子序列有几个字符。

        最左上角dp[0][0]、第一列dp[i][0]、第一行dp[0][j]很容易填写。

        对于普遍位置dp[i][j]分为下面几种情况：

        1>str1的第i个字符不在子序列中，dp[i][j]=dp[i-1][j]

        2>str2的第j个字符不在子序列中，dp[i][j]=dp[i][j-1]

        3>str1的第i个字符和str2的第j个字符都不在子序列中，dp[i][j]=dp[i-1][j-1]

        4>str1的第i个字符和str2的第j个字符都在子序列中，也就是满足天剑str1[i]==str2[j],dp[i][j]=dp[i-1][j-1]+1

        最后再取这四种情况的最大值保存在dp[i][j]中。

        由上面推理我们知道dp[i][j]={dp[i-1][j],dp[i][j-1],dp[i-1][j-1],dp[i-1][j-1]+1}。我们可以得知dp[i-1][j]>dp[i-1][j-1] 和dp[i][j-1]>dp[i-1][j-1]的，所以他情况3>我们就可以省略不写。

思想二：

        同样使用动态规划的思想。定义二维数组dp，行列分别表示字符串str的字符。dp[i][j]表示的含义：字符串str从从下标i~j最长回文子序列有几个字符。

        根据性质二维数组的左下部分不需要填写，并且左上到右下的对角线和对角线上衣对角线很容易填写出来。、

        对于普遍位置的dp[i][j]，可以分为下面几种情况：

        1>字符串str的第i位置不在最后的回文子序列中，dp[i][j]=dp[i+1][j]

        2>字符串str的第j位置不在最后的回文子序列中，dp[i][j]=dp[i][j-1]

        3>字符串str的第i和j位置不在最后的回文子序列中，dp[i][j]=dp[i+1][j-1]

        4>字符串str的第i和j位置在最后的回文子序列中，也就是满足条件str[i] == str[j]时，dp[i][j]=dp[i+1][j-1]+2

        最后再取这四种情况的最大值保存在dp[i][j]中。

        由上面推理我们知道dp[i][j]={dp[i+1][j],dp[i][j-1],dp[i+1][j-1],dp[i+1][j-1]+2}。我们可以得知dp[i+1][j-1]>dp[i+1][j] 和dp[i][j-1]>dp[i+1][j-1]的，所以他情况3>我们就可以省略不写。

代码

思想一代码：

    public static int maxLen1(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] str1 = str.toCharArray();
        char[] str2 = reverse(str1);
        return lcse(str1, str2);
    }
 
    public static char[] reverse(char[] str) {
        char[] reverse = new char[str.length];
        for (int i = 0; i < reverse.length; i++) {
            reverse[i] = str[str.length - 1 - i];
        }
        return reverse;
    }
 
    public static int lcse(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < str1.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
        }
        for (int j = 1; j < str2.length; j++) {
            dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (str1[i] == str2[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[str1.length - 1][str2.length - 1];
    }

思想二代码：

    public static int maxLen2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[][] dp = new int[str.length][str.length];
        for (int i = 0; i < str.length; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < str.length - 1; i++) {
            dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
        }
        for (int i = str.length - 2; i >= 0; i--) {
            for (int j = i + 2; j < str.length; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                if (str[i] == str[j]) {
                    dp[i][j] = Math.max(dp[i + 1][j - 1] + 2, dp[i][j]);
                }
            }
        }
        return dp[0][str.length - 1];
    }
 
    public static void main(String[] args) {
        String test = "A1BC2D33FG2H1I";
        System.out.println(maxLen1(test));
        System.out.println(maxLen2(test));
    }