516. 最长回文子序列

516. 最长回文子序列

1.想法

image.png

我们采用动态规划

1.建模

a.解:将f[n][n]数值填满
b.目标函数:f[0][n-1]最大
c.约束条件:必须为回文序列

2.子问题优化

f[i][j]代表了从i索引处开始,到j索引处结束,所代表的最大的回文序列长度

1)i == j的时候,
f[i][j] =1

2. i <j 的时候
   f[i][j] = max(f[k][j-1]+2,f[i][j-1] chs[k] == chs[j]

3.规约公式

2.代码实现

public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        char[] chs = s.toCharArray();
        for(int j=0;j<n;j++){
            for(int i=j;i>-1;i--){
                if(i == j)f[i][j]=1;   //i==j
                else{
                    int index = findMyIndex(chs,i,j);  //寻找K的索引
                    if(index == -1){
                        f[i][j] = f[i][j-1];  
                    }else{
                        f[i][j] = Math.max(f[i][j-1],f[index+1][j-1]+2);  //找出最大的值
                    }
                }
            }
        }
        return f[0][n-1];

    }
   //寻找K的索引
    private int findMyIndex(char[] chs, int i, int j) {  
        for(int index=i;index<j;index++){
            if(chs[index] == chs[j]){
                return index;
            }
        }
        return -1;

    }

3.改进其实不需要找到和chs[j]相同的k的索引

我们在计算的过程中已经把f[i][j-1]之前的和f[i+1][j]之间的都算过了,所以我们不需要找到k所在的索引
那么规约公式就变成了

代码

public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        char[] chs = s.toCharArray();
        for(int j=0;j<n;j++){
            for(int i=j;i>-1;i--){
                if(i == j)f[i][j]=1;
                else{
                    if (chs[i] == chs[j]) {
                        f[i][j] = f[i + 1][j - 1] + 2;
                    } else {
                        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    }
                }
            }
        }
        return f[0][n-1];

    }