#yyds干货盘点# 动态规划专题：最长回文子序列

web小门神 lv.1

发布时间：2023-02-06 21:05:49 344

相关标签： # 数据

1.简述：

描述

给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。

注：回文序列是指这个序列无论从左读还是从右读都是一样的。

本题中子序列字符串任意位置删除k（len(s)>=k>=0）个字符后留下的子串。

数据范围：字符串长度满足 #yyds干货盘点# 动态规划专题：最长回文子序列_子序列

进阶：空间复杂度 #yyds干货盘点# 动态规划专题：最长回文子序列_字符串_02 ，时间复杂度

输入描述：

输入一个字符串

输出描述：

输出最长回文子序列

示例1

输入：

abccsb

输出：

说明：

分别选取第2、3、4、6位上的字符组成“bccb”子序列是最优解

示例2

输入：

abcdewa

输出：

说明：

分别选取第一个和最后一个a，再取中间任意一个字符就是最优解

2.代码实现：

    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;
            char c1 = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    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];
    }

文章来源： https://blog.51cto.com/u_15488507/5814641

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。