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

网络安全监督员 lv.2

发布时间：2022-11-04 03:07:00 260

相关标签：

1.简述：

描述

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

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

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

输入描述：

输入一个字符串

输出描述：

输出最长回文子序列

示例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

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