题解 | #编号子回文II#

编号子回文II

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

这个问题可以使用动态规划来解决。我们可以定义一个二维数组 dp,其中 dp[i][j] 表示字符串 s 中从第 i 个字符到第 j 个字符的最长回文子序列的长度。然后我们可以遍历每一个位置,对于每一个位置,我们判断它的两边的字符是否相等,如果相等,那么它就是一个回文子序列。最后,我们遍历一遍 dp 数组,找到最长的回文子序列就是答案。

import java.util.*;


public class Solution {

    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                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];
    }

}
算法题刷刷刷 文章被收录于专栏

数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序

全部评论

相关推荐

01-26 22:20
已编辑
门头沟学院 Java
Java抽象带篮子:项目很nb了,现在好好准备八股和算法吧,早点找实习,可以看看我的置顶帖子。帖子里写了怎么改简历,怎么包装实习经历,还有2个高质量可速成的项目话术,和我的牛客八股笔记专栏
点赞 评论 收藏
分享
饼子吃到撑:当我看到外企的时候,我就知道这大概率可能是真的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务