题解 | #编号子回文II#

编号子回文II

https://www.nowcoder.com/practice/62e2d96d7b534d22a9b754005a4138a5

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]

全部评论

相关推荐

挣K存W养DOG:他真的很中意你,为什么不回他
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务