题解 | #编号子回文II#

知识点：动态规划

思路：

首先，我们创建一个二维整数数组f，f[i][j]表示字符串从第i个字符到第j个字符的最长回文子序列的长度。

然后，我们将对角线上的元素初始化为1，因为单个字符本身就是一个回文子序列。

接下来，我们使用两重循环遍历字符串s，从长度为2的子序列开始，逐步增加长度。对于每个长度len，我们遍历字符串s的每个起始位置i，并计算对应的结束位置j。如果s[i]与s[j]相等，那么如果子序列长度为2，则最长回文子序列的长度为2；否则，最长回文子序列的长度为s[i+1][j-1]的长度加2。如果s[i]与s[j]不相等，最长回文子序列的长度为s[i+1][j]和s[i][j-1]的较大值。

最终，f[0][n-1]即为给定字符串s的最长回文子序列的长度。

编程语言：java

import java.util.*;


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