516.最长回文子序列

给定一个字符串s，找到其中最长的回文子序列，并返回该序列的长度。可以假设s的最大长度为1000。

解题思路：动态规划

超赞的解题思路

dp 数组的定义是：在子串 s[i…j] 中，最长回文子序列的长度为 dp[i][j]。

class Solution {public int longestPalindromeSubseq(String s) {if(s == null || s.length() == 0) {return 0;}int n = s.length();//看成s1=s,s2=sint dp[][] = new int[n][n];//Arrays.fill(dp,0);//1.dp数组定义时，左下三角形默认值为0//2.初始化对角线元素for(int i = 0; i < n; i++) {dp[i][i] = 1;}//3.反着遍历（填充dp右上三角形的元素）：for(int i = n - 1; i >= 0; i--) {//j从i+1开始，因为对角线元素已经算出来了==1for(int j = i + 1; j < n; j++) {if(s.charAt(i) == s.charAt(j)) {// s[i] 和 s[j] 一定在最长回文子序列中dp[i][j] = dp[i + 1][j - 1] + 2;} else {// s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}//4.dp最右上角 = 整个 s 的最长回文子串长度return dp[0][n - 1];   }
}