题解 | #编号子回文II#

import java.util.*;


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

        for(int len=1;len<s.length();len++){
            for(int i=0;i+len<s.length();i++){
                if(s.charAt(i)==s.charAt(i+len)){
                    arr[i][i+len] = arr[i+1][i+len-1]+2;
                }else {
                    arr[i][i+len] = Math.max(arr[i+1][i+len],arr[i][i+len-1]);
                }
            }
        }
        return arr[0][s.length()-1];
    }
}

本题考察的知识点是动态规划，所用编程语言是java。

我们首先定义dp[i][j]表示字符串下标从i到j的回文串长度，

dp[i][j]=1,当i==j.

dp[i][j]=0 当i>j时。

dp[i][j] = max(dp[i+1][j],dp[i][j-1]) 当s[i]!=s[j]时。

dp[i][j] = dp[i+1][j-1]+2 当s[i]=s[j]