您的位置:首页 > 健康 > 养生 > leetcode:516 最长回文字序列 动态规划

leetcode:516 最长回文字序列 动态规划

2024/12/23 12:02:46 来源:https://blog.csdn.net/weixin_60214397/article/details/141939417  浏览:    关键词:leetcode:516 最长回文字序列 动态规划

516. 最长回文字序列

题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/

题目描述

给定一个字符串 s,找到 s 中最长的回文子序列。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "bbbab"               
输出: 4
解释: 一个可能的最长回文子序列是 "bbbb"。

示例 2:

输入: "cbbd"        
输出: 2
解释: 一个可能的最长回文子序列是 "bb"。

题目解析

s 中最长的回文子序列长度和s的子序列有关。

因此我们可以采用动态规划解决这个问题。

我们用dp[i][j]表示从i到j的最长回文子序列的长度。

初始化dp[i][i] = 1,表示一个字符就是回文子序列。

然后我们从i到j遍历,填充dp[i][j]。

状态转移方程如下:

如果s[i] == s[j],那么dp[i][j] = dp[i+1][j-1] + 2

如果s[i] != s[j],那么dp[i][j] = max(dp[i+1][j], dp[i][j-1])

我们返回dp[0][n-1],其中n是字符串s的长度,即为最长回文子序列的长度。

值得注意的是,我们在遍历填充dp时,由于dp[i][j]的值的计算依赖于dp[i+1][j-1]和dp[i][j-1]以及dp[i-1][j-1],因此我们需要按列,从下往上向前填充dp。

代码实现

Python版本:

class Solution(object):def longestPalindromeSubseq(self, s):n=len(s)dp=[[0]*n for _ in range(n)]for i in range(0,n):dp[i][i]=1for j in range (1,n):for i in range (j-1,-1,-1):if s[i]==s[j]:dp[i][j]=dp[i+1][j-1]+2else :dp[i][j]=max(dp[i+1][j],dp[i][j-1])return dp[0][n-1]

Go版本:

func longestPalindromeSubseq(s string) int {n:=len(s)dp:=make([][]int,n)for i:=range dp{dp[i]=make([]int,n)}for i:=0;i<n;i++{dp[i][i]=1}for j:=1;j<n;j++{for i:=j-1;i>=0;i--{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][n-1]
}

C++版本:

class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();auto dp=vector<vector<int>> (n,vector<int>(n));for(int i=0;i<n;i++){dp[i][i]=1;}for(int j=1;j<n;j++){for(int i=j-1;i>=0;i--){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][n-1];}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com