最长回文子序列

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

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

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var s string
    fmt.Scan(&s)
    dp:=make([][]int,len(s)+1)
    for i,_:=range dp{
        dp[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]{
                dp[i+1][j+1]=dp[i][j]+1
            }else{
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            }
        }
    }
    fmt.Println(dp[len(s)][len(s)])
}

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

发表于 2023-03-16 22:10:01 回复(0)