最长回文子序列—LPS(Sequence)

看了一些类似文章发现很多同学连子串，子序列的概念都是混淆的。
子序列：sequence，是不必连续的一组字符
子串：substring，是必须连续的一组字符

一般最长，最多，最大的关键字问题，都可能考虑用动规DP
DP的两个特征：最优子结构，重叠子问题
子结构需要分析题目特征，归纳状态方程。重叠子问题则一般使用空间换时间的方式能够解决。

最长回文子序列，最长回文子串，最长公共子序列 最长公共子串 最长递增子序列 等都可以使用DP解决

题目描述：

对一个字符串，求出它的最长回文子序列

分析：假设一个字符串google,可以看出LPS是goog.定义长度为n的一个字符串String的LPS为 L(0,n-1)，假如String的首尾相同L(0,n-1) = 2 + L(1,n-2),否则String的L(0,n-1) = max(L(0，n-2),L(1，n-1))因此分成了最优子结构问题。但是这里会重叠计算一些问题

Paste_Image.png

图中左右子树出现重复计算的操作，浪费时间。因此空间换时间，用一个二维数组的d[n][n]将计算过的子问题结果全部保存，最后的目的就是得到d[0][n-1]的值,只考虑的d[i][j]中i < j 的子序列，因此初始化全部为0并且对角线为1(只有自身当然算一个长度为1的子序列)。

Paste_Image.png

import java.util.Scanner;
//最后输出的是字符串生出LPS需要去除的字符个数
public class Solution{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String input = in.next();
            System.out.println(input.length() - getLps(input));
        }
    }
    public static int getLps(String string){
        char[] str = string.toCharArray(); 
        int n = str.length;
        int[][] dp = new int[n][n];
        int tmp = 0;
        for(int i=0; i<n; i++) dp[i][i] = 1;
        for(int i=1; i<n; i++){
            tmp = 0;
            for(int j=0; j+i<n; j++){
                if(str[j] == str[j+i]){
                    tmp = dp[j+1][j+i-1] + 2;
                }else{
                    tmp = Math.max(dp[j+1][j+i],dp[j][j+i-1]);
                }
//对i+1长度的子序列求出结果放入对应位置
                dp[j][j+i] = tmp;
            }
        }
        return dp[0][n-1];
    }
}

看到还有一种做法：就是用数组存一个String的倒置StringReverse，然后计算两个字符串的LCS(公共子序列),就是String的LPS，知乎上有数学证明:
<a>https://www.zhihu.com/question/34580085/answer/59552078</a>