516 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
动态规划
/**
* DP
*
* @param s
* @return
*/
public static int longestPalindromeSubseq(String s) {
if (s.length() == 0) return 0;
int n = s.length();
// dp[i][j] 表示从i到j的子序列的最长回文长度
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
char ch1 = s.charAt(i);
for (int j = i + 1; j < n; j++) {
char ch2 = s.charAt(j);
// 如果S[i]==S[j] 表示i~j的回文长度为i+1~j-1的范围内的长度
if (ch1 == ch2) {
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][n - 1];
}
5 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
示例 3：
输入：s = "a" 输出："a"
示例 4：
输入：s = "ac" 输出："a"
动态规划
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
boolean[][] dp = new boolean[s.length()][s.length()];
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < s.length(); j++) {
dp[i][j] = false;
}
dp[i][i] = true;
}
for (int i = s.length() - 2; i >= 0; i--) {
for (int j = i + 1; j < s.length(); j++) {
dp[i][j] = s.charAt(i) == s.charAt(j)
//小于3是因为aba一定是回文
&& (j - i < 3 || dp[i + 1][j - 1] == true);
// dp[i][j]为True，并且需要更新的话
if (dp[i][j] && end - start < j - i) {
end = j;
start = i;
}
}
}
return s.substring(start, end + 1);
}