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

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] 表示从字符串第 i 个字符到第 j 个字符的最长回文子序列的长度。

遍历字符串的每个字符，将所有单个字符作为回文子序列，即 dp[i][i] = 1。

从长度为2的子序列开始，通过递推求解更长的回文子序列。对于每个子序列，如果头尾字符相同，则当前子序列的最长回文子序列长度为内部子序列的最长回文子序列长度加上2；如果头尾字符不同，则当前子序列的最长回文子序列长度为去掉头字符或去掉尾字符的子序列的最长回文子序列长度的较大值。具体地，通过状态转移方程 dp[i][j] = dp[i + 1][j - 1] + 2 或 dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]) 来更新 dp[i][j] 的值。

返回整个字符串的最长回文子序列的长度，即 dp[0][n - 1]，其中 n 为字符串的长度。