看了一些类似文章发现很多同学连子串，子序列的概念都是混淆的。
子序列：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>
