最长回文子序列 递归与动态规划
public static int longestPalindromeSubseq(String s) {
char[] chars = s.toCharArray();
int n = chars.length;
int[][] dp = new int[n][n];
//先约束边界 dp[L][R]
dp[n-1][n-1] = 1;
//约束的下边界，那就从上边界开始，直至下边界的前一位
//此处初始化对角线以及倒数第二的对角线，在上面的分析中已经提到过范围约束，不可能存在对角线左下方的情况
for (int i = 0; i < n-1; i++) {
dp[i][i]=1;
dp[i][i+1] = chars[i]==chars[i+1]?2:1;
}
//dp矩阵需画图
for (int i = 0; i < n - 3; i++) {
for (int j = i+2; j < n; j++) {
//将原本的递归，转换为动态规划
// int res1 = process(chars,i+1,j-1);
int res1 = dp[i+1][j-1];
// int res2 = process(chars,i,j-1);
int res2 = dp[i][j-1];
// int res3 = process(chars,i+1,j);
int res3 = dp[i+1][j];
// int res4 = chars[i]==chars[j]?2+res1:0;
int res4 = chars[i]==chars[j]?2+res1:0;
//当前要求的值是dp[i][j]
dp[i][j] = Math.max(Math.max(res1,res4),Math.max(res2,res3));
}
}
return dp[0][n-1];
}