来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
题目描述：
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
思路分析：
假设当前字符串s中的最长回文子序列为dp[i][j], i,j代表字符索引下标，那么它的上一个回文子序列必然在[i+1][j],[i][j-1],[i+1][j-1]这三个字符序列之中。
如果s[I] == s[j]，则dp[i][j] = dp[i+1][j+1] + 2;
如果s[i] != s[j], 则dp[i][j] = dp[i+1][j]; // 跳过第i个字符
如果s[i] != s[j], 则dp[i][j] = dp[i][j - 1]; // 跳过第j个字符
不相等时有两种选择，该选择哪一个还是两个都选择呢，因为这里只是求的最长回文子序列的长度，因此每个回文子序列中的回文子序列也必须是最长的，Math.max(dp[i+1][j],dp[i][j-1])取大的那个，相等就随便取一个。如果题目要求输出最长回文子序列，相等就不能随便取了，而是两个都应该记录。
例如字符串s [a,b,c,b,d,a](数组形式方便表示)，最长回文子序列长度5，最长回文子序列abcbda，dp[0][5],
则它的上一个回文子序列:
因为s[0] == s[5],则dp[0 + 1][5 - 1] 为bcbd
因为s[1] != s[4] 所以两种可能
- dp[1 + 1][4]跳过左边字符为cbd
- dp[1][4-1]跳过右边字符为bcb.
可以看到bcb回文序列为2，cbd为1(单个字符回文长度为1)，因此应该选择dp[1][3]也就是bcb）
因为s[1] == s[3],则dp[1+1][3-1]为c就结束了。
将整个过程倒过来，从回文长度为1的字符开始,即可求解。
代码实现：
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
for (int i = len - 2; i >= 0; i--) {
char left = s.charAt(i);
for (int j = i + 1; j < len; j++) {
char right = s.charAt(j);
if (left == right) {
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][len - 1];
}
}
