leetcode 516. 最长回文子序列

题目描述：给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
解题步骤：解决此类问题可以采用动态规划 dp[i][j]表示从第i个字符到第j个字符之间的最长回文子串。该问题类似于01背包问题
1、 状态定义：dp[i][j] 表示从第i个字符到第j个字符之间的最长回文子串的长度
2、 状态转移方程：
如果第i个字符和第j个字符相同，则等于第i+1到j-1字符之间的最长子串加上2
dp [i][j] = dp [i + 1][j - 1] + 2 （s[i]==s[j]）
如果第i个字符和第j个字符不同，则需要计算i和j之间子串的最大值，也即是分别i向右移动或j向左移动
dp [i][j] = max(dp[i + 1][j], dp[i][j - 1]) (s[i]!=s[j])
由于在计算dp[i][j]的时候需要提前知道dp[i+1][j]所以i从字符串最后往前遍历，dp[i][j-1]需要知道[j-1]所以j需要从前往后遍历，并且为了使计算不重复，j需要从i+1开始。
3、 初始化：dp[i][i] = 1 单个字符的最长回文序列是 1，只需要在第一个for循环即i对应的for循环中赋值就行了

4、 输出：dp[0][s.length-1]
代码：

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