题解 | #编号子回文II#

题目考察的知识点是：

动态规划。

题目解答方法的文字分析：

先判断长度是否为0，定义一个长度为n的数组dp，将数组设置成1，使用双循环将数据填充到数组中，最后取数组中第一组的倒数第一个数据的值。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int longestPalindromeSubseq (String s) {
        // write code here
        if (s == null || s.length() == 0) {
            return 0;
        }
        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];
    }
}