516.最长回文子序列（中等）

思路：

从长度为2开始，每个长度从左到右遍历一遍，得到该长度是否满足（重叠子问题）

长度加1，比较是否满足，若不满足，则取前一次长度的最优解（最优解问题）

代码：

class Solution {
    public int longestPalindromeSubseq(String s) {
		int n=s.length();
		
		//这里的dp表示长度，不表示数值
		int[][] dp=new int[n][n];
		
		//将dp的对角线元素置为1，意思是单个元素时，长度为1
		//因为是二维数组,不能用Arrays.fill()直接填满为1
		for(int i=0;i<n;i++){
			dp[i][i]=1;
		}
		
		//从2开始，逐个增加长度，不是累加，而是每次都是重新选值
                //len的条件设置为<=n
		for(int len=2;len<=n;len++){
			//从头开始遍历
			for(int i=0;i<n-len+1;i++){
                                //设置j为对应i这个头元素的尾元素
				int j=i+len-1;
				//若头尾的字符相同，符合条件，长度直接+len
				if(s.charAt(i)==s.charAt(j)){
					//dp[i+1][j-1]表示中间的最优解
					dp[i][j]=2+(len==2?0:dp[i+1][j-1]);
				}else{
					dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
				}
			}
		}
                //此时0~n-1是最优解，而不是还有1的可能
		return dp[0][n-1];
    }
}
           

分解：

1）这里的dp是第二种形式：当前值依赖于前面所有计算好的值

区间规划：一般用 dp[i][j] 代表从第 i 个位置到第 j 个位置之间的最佳状态或结果

dp表示的是从第一个数到第二个数之间的长度，则下标设为n即可，不用设为n+1，不会出现下标溢出问题

2）设置对角线为1，表示单个元素时，包含自身，回文子序列长度为1

for(int i=1;i<n;i++){
    dp[i][i]=1;
}
           

3）只设置双重遍历（len,i）

只需要头i从头到尾遍历即可，j只需要随每次i的变化而动，不需要j进行遍历

for(int len=2;len<=n;len++)
	for(int i=0;i<n-len+1;i++)          
	    int j=i+len-1;
           

4）核心代码：

当len==2时，头尾满足条件，则长度为2

当len==3时，头尾满足条件，则长度为2+中间的最优解dp[i+1][j-1]

                      头尾不满足条件，则长度为i和j中间的最优解dp[i+1][j]或dp[i][j-1]

if(s.charAt(i)==s.charAt(j)){
    //dp[i+1][j-1]表示中间的最优解
    dp[i][j]=2+(len==2?0:dp[i+1][j-1]);
}else{
    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}