题解 | #编号子回文II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestPalindromeSubseq (String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int k = 1; k < n; k++) {
            for (int i = 0; i + k < n; i++) {
                if (s.charAt(i) == s.charAt(i + k)) {
                    dp[i][i + k] = dp[i + 1][i + k - 1] + 2;
                } else {
                    dp[i][i + k] = Math.max(dp[i + 1][i + k], dp[i][i + k - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

本题知识点分析：

1.动态规划

2.数组遍历

3.API函数

4.数学模拟

本题解题思路分析：

1.定义一个二维数组dp，dp[i][j]表示字符串s从下标i到下标j的最长回文子序列的长度。

2.当s.charAt(i)等于s.charAt(i + k)时，说明子串的首尾字符相同，此时可以将首尾字符同时加入最长回文子序列中，所以此时dp[i][i + k]的值等于dp[i + 1][i + k - 1] + 2。

3.当s.charAt(i)不等于s.charAt(i + k)时，说明子串的首尾字符不同，此时需要在子串的左侧或右侧选择一个最长回文子序列，所以取dp[i + 1][i + k]和dp[i][i + k - 1]的较大值作为dp[i][i + k]的值。

4.最后返回dp[0][n - 1]，整个字符串的最长回文子序列的长度。

本题使用编程语言: Java