题解 | #编号子回文II#

知识点:动态规划

解题思路:

首先定义一个二维数组dp，其中dp[i][j]表示从字符串s的第i个字符到第j个字符的最长回文子序列的长度。

在dp数组中，i的取值范围是从n-1到0，j的取值范围是从i到n-1（其中n是字符串s的长度）。//最后需要的是dp[0][n-1]

状态转移方程。当s[i]==s[]时，dp[i][j]=dp[i+1][j-1] + 2。否则，dp[i][j]=max(dp[i+1][j],dp[i][j-1])。

最后，我们只需要返回dp[0][n-1]即可，其中n是字符串s的长度。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestPalindromeSubseq (String s) {
        int n = s.length();
        //从i-》j的最长回文子字符串长度为dp[i][j]
        int[][] dp = new int[n][n];
        //注意循环start和end,最后需要的是dp[0][n-1]
        for (int i = n - 1; i >= 0; i--) {
            // 单个字符
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                //字符一致时长度+2
                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];
    }
}