题目链接
题目描述
实现代码
动态规划思想:记dp[i][j]表示从i到j索引位置的子串的最长回文子序列长度,则有两种情况:
- s[i] == s[j]时:dp[i][j] = dp[i-1][j-1] + 2
- s[i] ≠ s[j]时:dp[i][j] = max(dp[i+1][j], dp[i][j-1])
初始化条件:dp[i][i] = 1
实现代码:
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
char c1 = s.charAt(i);
for (int j = i + 1; j < n; j++) {
char c2 = s.charAt(j);
if (c1 == c2) {
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];
}
}