1. 题目

2. 思路

(1) 动态规划

• dp[i][j]表示字符串s的下标为[i,j]的最长回文子序列的长度。
• 若chars[i]==chars[j]，则dp[i][j]=dp[i+1][j-1]+2；否则，dp[i][j]取dp[i][j-1]和dp[i+1][j]中较大值。

3. 代码

public class Test {public static void main(String[] args) {}
}class Solution {public int longestPalindromeSubseq(String s) {char[] chars = s.toCharArray();int n = chars.length;int[][] dp = new int[n][n];for (int i = n - 1; i >= 0; i--) {dp[i][i] = 1;for (int j = i + 1; j < n; j++) {if (chars[i] == chars[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);}}}return dp[0][n - 1];}
}