首页 > 试题广场 >

最长回文子序列

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

热度指数：4698 时间限制：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，再取中间任意一个字符就是最优解

算法知识视频讲解

JavaScript

别卷啦！

其实就是求ｓ和ｓ的逆序的最长公共子序列的。转化成最长公共子序列问题就迎刃而解了。

二维数组：

dp[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。状态转移方程

s[i]和s[j]相同时，dp[i][j]为dp[i-1][j-1] + 2

不相同时，dp[i][j]为dp[i][j-1]和dp[i+1][j]的最大值

function longestPalindromeSubSeq( s ) {
    // write code here
    if(!s) return 0
    let len = s.length
    let dp = Array.from(new Array(len),()=>new Array(len).fill(0))
    for(let i = len-1;i>=0;i--){
        dp[i][i] = 1
        for(let j = i+1;j<len;j++){
            if(s[i]==s[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][len-1]
}

编辑于 2021-01-22 19:27:29 回复(0)

Java

pein531

动态规划

子序列的最值问题可以想到范围上的尝试模型，dp[i][j]表示s[i:j]上的最长回文子串长度，要求这个长度需要按端点进行可能性的划分：

如果构成的最长回文子串既包括s[i]又包括s[j]，那就要求s[i]=s[j]才能构成回文。而包括端点也能构成回文，就说明可以在s[i+1:j-1]的最长回文子序列的基础上增加两个字符，因此dp[i][j]=dp[i+1][j-1]+2。
如果s[i]与s[j]不同，那这两个字符的加入就无法增加回文子序列的长度，因此dp[i][j]直接从dp[i][j-1]和dp[i+1][j]中较大的那个状态转移过来就行。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    public int longestPalindromeSubSeq (String s) {
        // write code here
        int n = s.length();
        int[][] dp = new int[n][n];     // dp[i][j]表示s[i:j]上的最长回文子串长度
        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];
    }
}

复杂度分析

两层循环，时间复杂度为O(n²)，开辟的dp数组为二维表，空间复杂度也为O(n²)。

发表于 2021-12-15 16:45:14 回复(0)

Java

叫我骑天大圣

子序列：下标可以不连续
子串：下标连续的一段

区间dp可解：先求小区间的最优解，再求大区间的最优解。

定义状态：
dp[n][n]//n=字符串长度
dp[i][j]=区间[i,j]上最长回文子序列的长度

状态转移方程：
if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);

If 区间[i,j]两端字符一样，则可构成回文，[i,j]最优解=区间[i+1,j-1]最优解长度+2;  Else 否则，取[i,j]区间上最大的解。直接看[i,j-1]和[i+1，j]这两区间谁的解最大就行，
因为它俩的最优解涵盖[i,j]区间上所有子区间的解

时间复杂度O(n^2)，n<5000，勉强能过。

public int longestPalindromeSubSeq (String s) {
        // write code here
        int n=s.length();
        int[][] dp=new int[n+1][n+1];
        for(int len=1;len<=n;len++){//区间长度递增，从小区间到大区间依次求解
            for(int l=0;l<n;l++){   //区间左端点left
                int r=l+len-1;      //右端点right
                if(r>=n) break;
                if(l==r) dp[l][r]=1;
                else if(s.charAt(l)==s.charAt(r)) dp[l][r]=dp[l+1][r-1]+2;
                else{
                    dp[l][r]=Math.max(dp[l][r],dp[l][r-1]);
                    dp[l][r]=Math.max(dp[l][r],dp[l+1][r]);
                }
            }
        }
        return dp[0][n-1];
    }

编辑于 2021-02-25 09:45:22 回复(0)

达拉崩吧、

使用动态规划 O（n^2）,O（n^2）

function longestPalindromeSubSeq(str) {
    const len = str.length;
    const dp = Array.from(new Array(len), () => new Array(len).fill(0));
    for (let i = 0; i < len; i++) {
        dp[i][i] = 1;
    }
    let max = 1;
    for (let i = len - 2; i >= 0; i--) {
        for (let j = i + 1; j < len; j++) {
            if (j === i + 1) {
                dp[i][j] = str[i] === str[j] ? 2 : 0;
            } else {
                if (str[i] === str[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
            max = Math.max(max, dp[i][j]);
        }
    }
    return max;
}

发表于 2023-08-08 16:11:39 回复(0)

小谷围做题家

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string 一个字符串由小写字母构成，长度小于5000
 * @return int
*/
func longestPalindromeSubSeq( s string ) int {
    mat:=make([][]int,len(s)+1)
    for i,_:=range mat{
        mat[i]=make([]int,len(s)+1)
    }
    for i:=0;i<len(s);i++{
        for j:=0;j<len(s);j++{
            if s[i]==s[len(s)-j-1]{
                mat[i+1][j+1]=mat[i][j]+1
            }else{
                mat[i+1][j+1]=max(mat[i][j+1],mat[i+1][j])
            }
        }
    }
    return mat[len(s)][len(s)]
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-03-14 23:27:59 回复(0)

企鹅暴打皮卡丘

编译失败求助，我不理解为什么系统给的函数说未定义

发表于 2022-10-08 10:37:20 回复(0)

C++

Dreams0000

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        // write code here
        return longestPalindromeSubSeqV1(s);
    }
    // 01 dp
    int longestPalindromeSubSeqV1(string s) {
        // write code here
        // dp[i][j]表示[i,j]范围内的字符串的最大回文序列长度
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        
        // dp[i][j]的对角线需要初始化为1
        for (int i =0; i <dp.size(); ++i) {
            dp[i][i] =1;
        }
        for (int i =s.size()-1; i >=0; --i) {
            // 这里j =i+1开始，避免后面dp[i+1][j-1]发生数组越界
            for (int j =i+1; j <s.size(); ++j) {
                if (s[i] ==s[j]) {
                    dp[i][j] =dp[i+1][j-1] +2;
                }
                else {
                    dp[i][j] =max(max(dp[i+1][j], dp[i][j-1]), dp[i+1][j-1]);
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

发表于 2022-09-11 10:56:02 回复(0)

C++

等一个offer！

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        int n = s.size();
        //dp[i][j]表示s[i..j]内的最长回文子序列的长度
        vector<vector<int>>dp(n,vector<int>(n));
        if(n<2) return n;
        for(int i=n-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i+1;j<n;j++){
                if(s[i]==s[j]){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};

发表于 2022-04-10 15:56:02 回复(0)

C++

好好小唐

思路：翻转后求最大公共子串

class Solution {

public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string 一个字符串由小写字母构成，长度小于5000
* @return int
*/
int longestPalindromeSubSeq(string s) {
// write code here
int l = s.size();
if(l==0||l==1)
return l;

int ans = 0, index = 0;
vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1, 0));
string B = s;
reverse(B.begin(), B.end());
for(int i = 1; i <= l; i++)
for(int j = 1; j <= l; j++){
if(s[i - 1] == B[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
ans = max(ans,dp[i][j]);


}
return ans;
}
};

发表于 2022-01-02 15:43:22 回复(0)

Java

惠灵顿靖

public class Solution {
// dp[i][j]定义为：字符串从i到j是含有回文子序列的长度
// 1、当i==j时，dp[i][j]==1
// 2、当j-i<=2时，如s[i]==s[j]，dp[i][j] = j-i+1
// 3、当j-i>2时,  如s[i]==s[j]，dp[i][j] = dp[i+1][j-1]+2
// 4、如s[i]!=s[j]时，dp[i][j] = max(dp[i][j-1], dp[i+1][j])
// 由于递推公式：
// dp[i][j] = dp[i+1][j-1]+2，i要从大的数值，j要从小的数值开始计算
    
    public int longestPalindromeSubSeq (String s) {
        // write code here

        int[][] dp=new int[s.length()][s.length()];
        for(int i=0;i<s.length();i++)dp[i][i]=1;
        
        for (int i=s.length()-1;i>=0;i--){
            for (int j=i+1;j<s.length();j++){
                if(j-i<=2){
                    if (s.charAt(i)==s.charAt(j))dp[i][j]=j-i+1;
                    else dp[i][j]=Math.max(dp[i][j-1], dp[i+1][j]);
                }
                else {
                    if (s.charAt(i)==s.charAt(j))dp[i][j]=dp[i+1][j-1]+2;
                    else dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
}

发表于 2021-10-02 10:15:06 回复(0)

Python 3

你可以的冲

python在5000个‘s’的时候超时了啊。。。咋回事

class Solution:
    def longestPalindromeSubSeq(self , s ):
        # write code here
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][-1]

发表于 2021-09-21 12:18:57 回复(0)

害群之马

class Solution {
public:
    int longestPalindromeSubSeq(string s) {
        // 假设dp[i][j] 表示以第i个元素开始，元素j结尾的最长子序列的长度
        int n=s.size();
        if(n<=1) return 0;
        const int N=n;
        int dp[N][N];
        
        for(int i=0;i<n;i++) dp[i][i]=1;
        
        for(int i=N-1;i>=0;i--){
            for(int j=i+1;j<N;j++){
                //不包含最后一个元素 dp[i][j]=dp[i][j-1]
                // 或者不包含第一个元素
                //如果包含最后一个元素dp[i][j]=dp[start+1][j-1]+1
                if(s[i]==s[j]){
                    if(j==i+1) dp[i][j]=2;
                    else  dp[i][j]=dp[i+1][j-1]+2;
                }
                else{
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
                
            }
        }
        return dp[0][n-1];
    }
};

发表于 2021-06-14 22:11:31 回复(0)

C/C++

codewind

#define max3(i,j,k)  max(i,max(j,k))
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * dp[i][j] = max(dp[i+1][j] , dp[i][j-1])
      if si==sj  dp[i][j] = max(dp[i][j], 2 + dp[i+1][j-1]  )
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    int longestPalindromeSubSeq(string s) {
        // write code here
        int n = s.size();
        if(n==0) return 0;
        vector<vector<int>> dp(n+1,vector<int>(n+1));
        for(int i=n-1;i>=0;--i) {
            dp[i][i] = 1;
            for(int j=i+1;j<n;++j) {
                if(s[i] == s[j]) {
                    dp[i][j] = max(dp[i][j],dp[i+1][j-1]+2);
                }else {
                    dp[i][j] = max3(dp[i][j],dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        
        return dp[0][n-1]; 
        
    }
};

发表于 2021-04-06 22:11:45 回复(0)

Python

浮埃特

class Solution:
    def longestPalindromeSubSeq(self , s ):
        # write code here
        dp = [[0] * len(s) for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
            for j in range(i-1, -1, -1):
                if s[j] == s[i]:
                    if j+1 == i:
                        dp[j][i] = 2
                    else:
                        dp[j][i] = max(dp[j][i], dp[j+1][i-1] + 2)
                else:
                    dp[j][i] = max(dp[j][i], dp[j+1][i], dp[j][i-1])
        return dp[0][len(s)-1]

编辑于 2021-04-04 20:50:01 回复(1)

孙思源

因为是bccb呀

发表于 2021-02-22 16:52:03 回复(1)

牛客68124586号

样例输出的为什么是4啊？

发表于 2021-01-27 20:39:49 回复(1)

牛客313054358号

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string 一个字符串由小写字母构成，长度小于5000
* @return int
*/
public int longestPalindromeSubSeq(String s) {
// write code here
cache = new int[s.length()][s.length()];
return f(s, 0, s.length() - 1);
}

private int[][] cache;

public int f(String s, int i, int j) {

int integer = cache[i][j];
if (integer != 0) {
return integer;
}
if (i == j) {

return cache[i][j]= 1;
}
if (i == j - 1) {
if (s.charAt(i) == s.charAt(j)) {

return cache[i][j]=2;
} else {
return cache[i][j]= 1;
}
}
if (s.charAt(i) == s.charAt(j)) {
int i1 = 2 + f(s, i + 1, j - 1);

return cache[i][j] = i1;
} else {
int max = Math.max(f(s, i + 1, j), f(s, i, j - 1));

return cache[i][j]= max;
}
}
}

发表于 2021-01-16 16:03:51 回复(1)

提交观点

问题信息

动态规划

上传者：牛客301499号

难度：

17条回答 101收藏 3380浏览

通过挑战的用户

查看代码

牛客93777...

2022-09-14 23:08:59
西方不胜

2022-09-14 22:09:57
威化饼的一隅

2022-09-14 09:12:30
Asphyxiay

2022-09-14 02:06:35
牛客27179...

2022-09-13 20:35:40

最长回文子序列

输入

输出

说明

输入

输出

说明

动态规划

复杂度分析

问题信息

热门推荐

通过挑战的用户

相关试题