我要招人

去企业版

首页 > 试题广场 >

最长回文子序列

[编程题]最长回文子序列

热度指数：2362 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

数据范围：字符串长度满足 $1 \le n \le 1000$

进阶：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^2)$

输入描述:

输入一个字符串

输出描述:

输出最长回文子序列

示例1

输入

abccsb

输出

说明

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

示例2

输入

abcdewa

输出

说明

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

算法知识视频讲解

破竹GYH

发表于 2022-04-25 22:40:47

#include<bits/stdc++.h> using namespace std; int main() { string s; cin >> s; vector<vector<int> >dp(s.size(),vect 展开全文

fred-coder

发表于 2022-02-20 18:20:25

二维 dp 问题; 设置二维 dp， dp[i][j] 表示以 i 为开始, j 为结束的回文子序列的最长长度; 当 s[i] = s[j] 时, dp[i][j] 由 dp[i + 1][j - 1] 转移过来 + s[i] 和 s[j] 的长度 2 当 s[i] != s[j] 时, dp[ 展开全文

云白1

发表于 2023-08-19 10:58:25

import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new S 展开全文

wwwkal

发表于 2022-04-21 00:27:32

相当于求该字串与其翻转后的字串的最长公共子序列 #include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int max 展开全文

CCNWY

发表于 2022-12-01 21:45:00

package main import "fmt" func solution(str string) int { dp := make([][]int, len(str)) for i := range dp { dp[i] = make([]int, len(str)) } fo 展开全文

赫he

发表于 2023-07-10 21:39:54

dp[i][j]表示字符串s的下标范围[i,j]内的最长回文子序列的长度，假设字符串s的长度为n，当时，才满足dp[i][j]>0，否则dp[i][j]=0。初始化：由于任何长度为1的子序列都是回文子序列，所以对于任意的，都有dp[i][i]=1状态转移：当i<j时，计算dp[i][j] 展开全文

哑巴湖大水怪12580

发表于 2024-04-08 16:53:56

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = 展开全文

牛客211361839号

发表于 2022-05-10 11:42:47

function HWstr(str) { n = str.length; if (n == 1) return 1; var dp = Array.from(Array(n), () => Array(n).fill(0)); for 展开全文

Ivy2019

发表于 2022-08-27 17:11:22

最长回文子序列介绍：https://blog.csdn.net/ten_sory/article/details/79798064 直接套用这个递归的方法会部分用例超时。参考评论区的题解可以高效解决： //dp[i][j]指字符串s在[i, j]范围内最长的展开全文

静寂旮旯

发表于 2022-04-28 14:37:11

解题思路：建立模型为最长公共子序列。则只要求出s和sr（倒序）的最长公共子序列即可。一般情况：dp[i][j]=max(dp[i−1][j−1]+(int)(s[i]==sr[j]),max(dp[i−1][j],dp[i][j−1]))dp[i][j] = max(dp[i-1][j-1]+ 展开全文