思路分析
关于”回文串“的问题，是面试中常见的，本文提升难度，讲一讲”最长回文子序列“问题，题目很好理解：
输入一个字符串 s，请找出 s 中的最长回文子序列长度。
比如输入 s="aecda"，算法返回3，因为最长回文子序列是 "aca"，长度是3。
这个问题对 dp 数组的定义是：在子串 s[i...j] 中，最长回文子序列的长度为 dp[i][j]。一定要记住这个定义才能理解算法。
为什么这个问题要这样定义二维的 dp 数组呢？找状态转移需要归纳思维，说白了就是如何从已知的结果推出未知的部分，这样定义容易归纳，容易发现状态转移关系。
具体来说，如果想求 dp[i][j]，假设知道了子问题 dp[i+1][j-1] 的结果( s[i+1...j-1] 中最长回文子序列的长度)，是否能想办法算出 dp[i][j] 的值( s[i...j] 中最长回文子序列的长度)呢？
可以！这取决于 s[i] 和 s[j] 的字符：
如果它俩相等，那么它俩加上 s[i+1...j-1] 中的最长回文子序列就是 s[i...j] 的最长回文子序列：
如果它俩不相等，说明它俩不可能同时出现在 s[i...j] 的最长回文子序列中，那么把它俩分别加入 s[i+1...j-1]中，看看哪个子串产生的回文子序列更长即可：
以上情况写成代码就是这样：
if (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] = max(dp[i+1][j], dp[i][j-1])
至此，状态转移方程就写出来了，根据 dp 数组的定义，我们要求的就是 dp[0][n-1]，也就是整个 s 的最长回文子序列的长度。
代码实现
首先明确基本情况，如果只有一个字符，显然最长回文子序列长度是1，也就是 dp[i][j] = 1 (i == j)。因为 i 肯定小于或等于 j，所以对于那些 i > j 的位置，根本不存在什么子序列，应该初始化为0。另外，看看刚才写的状态转移方程，想求 dp[i][j] 需要知道 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1]这三个位置；再看看我们确定的基本情况，填入 dp 数组之后是这样的：
为了保证每次计算 dp[i][j]，左下右方向的位置已经被计算出来，只能斜着遍历或者反着遍历。这里选择反着遍历，代码如下：
package DynamicProgramming;
// leetcode 516 最长回文子序列
public class LCSS {
public int longestPalindromeSubseq(String s) {
int n = s.length();
// 创建 dp 数组
int[][] dp = new int[n][n];
// base case
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 反向遍历保证正确的状态转移
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; 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]);
}
}
}
// 整个 s 的最长回文子序列长度
return dp[0][n - 1];
}
public static void main(String[] args) {
LCSS lcss = new LCSS();
int len = lcss.longestPalindromeSubseq("aecda");
System.out.println(len);
}
}
