Java 题解 | #编号子回文II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int longestPalindromeSubseq (String s) {
        // write code here
        int n = s.length();
        int[][] dp = new int[n][n];

        // 单个字符是回文子序列
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }

        // 从长度为 2 的子序列开始递推
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i < n - len + 1; ++i) {
                int j = i + len - 1;
                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];
    }
}

编程语言是Java。

该题考察的知识点是动态规划。动态规划是一种解决问题的算法思想，通常用于求解具有重叠子问题和最优子结构性质的问题。

这段代码实现了求解最长回文子序列的长度。初始化一个二维数组dp，其中dp[i][j]表示字符串s在区间[i, j]内的最长回文子序列的长度。遍历字符串s，将所有单个字符作为回文子序列（长度为1），通过逐步增加子序列的长度，并将结果保存在dp数组中。在计算过程中，当遇到s[i] == s[j]时，说明当前字符可以成为回文子序列的一部分，长度加2，并且在去掉两个端点后继续判断子序列是否是回文的。当遇到s[i] != s[j]时，需要判断去掉首字符或尾字符后，哪个子序列的长度更长，将较长的那个值赋给dp[i][j]。最终，返回dp[0][n-1]即为字符串s的最长回文子序列的长度。