题解 | 最长回文子序列

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        System.out.println(longestPalindromeSubseq(s));
    }
    
    public static 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;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    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];
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

输入处理：使用 Scanner 读取输入的字符串。

动态规划数组初始化：二维数组 dp 用于存储子问题的结果，其中 dp[i][i] 初始化为1，因为单个字符本身就是一个回文。

填充动态规划数组：从字符串的末尾开始遍历，确保在计算当前子问题时，所有子子问题已经解决。对于每个字符对 (i, j)，根据字符是否相等来更新 dp 数组。

返回结果：最终结果存储在 dp[0][n-1] 中，表示整个字符串的最长回文子序列长度。