最长回文子序列_动态规划

题解

看了网上的很多个博客，还是不会，原因代码没有说明实际意义。

1. 如下的代码，从一个字符开始，首先一个字符一定是一个回文序列，他的长度是1

2. 如果确定了一个字符串，比如"adjddd",他的回文序列最大长度是4，那么他的两端再加上一个任意的字符，比如‘t’,"tadjdddt",那么它的长度就是6了。

3. 如果确定两端字符不同，那么2一定不成立，那么回文序列要让它尽可能长，取下子问题的结中最大的即可，那就损失一个长度([i][j-1],[i+1][j])找最大即可。

4. 不得不说，dp[i][j]代表的含义是字符字串s[i:j+1]对于该问题的解，即子问题的解。

5. 由于最低限度的问题：即只有一个字符的时候，我们知道它的解是确定的，所以这个问题可以用递归

   class Solution {
    public int longestPalindromeSubseq(String s) {
        if(s==null || s.length()==0) return 0;
   
        int len = s.length();
        // dp[i][j] 代表是字符串[i:j+1],子串的最长回文序列个数
        int[][] dp = new int[len][len];
   
        for(int i=0;i<len;i++){//一个字符一定是一个回文序列
            dp[i][i] = 1;
        }
   
        // 逐渐扩大子问题的范围
        for(int index=1;index<len;index++){
            int i=0;
            int j=index;
            while(i<len&&j<len){
                if(s.charAt(i) == s.charAt(j)){ //新增两边的数据相等就可以加上2
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{ // 两边数据不等的话，找出长度减一的子序列的最大值
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
                i++;
                j++;
            }
        }
   
        // 最终得出从1到n长度的序列的结果
        return dp[0][len-1];
    }
   }

   

   递归的解法

   class Solution{
    private String str;
    public int longestPalindromeSubseq(String s) {
        this.str = s;
        if(str == null || str.length() == 0){
            return 0;
        }
        return longestSub(0,s.length()-1);
    }
   
    public int longestSub(int start,int end) {
        System.out.println(start + ":" + end);
        if(start == end){
            return 1;
        }
        if(start > end){
            return 0;
        }
        // 走到这里说明他的长度至少是2
        if(str.charAt(start)==str.charAt(end)){
            return 2+longestSub(start+1,end-1);
        }else{ // 不能同时包含两端了，那么只包含一个的最大值
            return Math.max( longestSub(start+1,end),longestSub(start,end-1));
        }
    }

   这种方法对于小数据类是非常的OK的，但是一旦字符串的长度是几百几千，那么栈空间将会爆战，不会出现正确 结果
   
   
   长度为6的递归调用已经很恐怖了，如果一直走第二条路，最坏情况，指数式增长，所以，这个只供理解就好了。