首页 > 极客资料 博客日记
线性dp:LeetCode516 .最长回文子序列
2024-09-07 16:30:04极客资料围观22次
文章线性dp:LeetCode516 .最长回文子序列分享给大家,欢迎收藏极客之家,专注分享技术知识
LeetCode516 .最长回文子序列
题目叙述:
给你一个字符串 s
,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
示例 1:
输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。
示例 2:
输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。
提示:
1 <= s.length <= 1000
s
仅由小写英文字母组成
动态规划思路
-
我们在上文中已经介绍了回文子串,那么我们可以沿用
回文子串
的思想解决这道题,但是我们首先得明确回文子串
和回文子序列
的区别 -
LeetCode647.回文子串
求的是回文子串,而本题要求的是回文子序列, 要搞清楚这两者之间的区别。 -
回文子串是要连续的,回文子序列可不是连续的! 回文子串,回文子序列都是动态规划经典题目。
-
回文子串,可以做这两题:
-
647.回文子串
-
5.最长回文子串
-
思路其实是差不多的,但本题要比求回文子串简单一点,因为情况少了一点。
动规五部曲分析如下:
1.确定状态变量及其含义
- 我们设立dp数组,dp[i]] [j] 表示s字符串在
[i,j]
范围内最长回文子序列的长度。(j
>=i
) - 那么我们确立了状态变量
dp[i][j]
,那么我们就要开始处理递推公式和如何初始化了
2.确定递推公式
- 在这里,我们最重要的就是判断
s[i],s[j]
之间的关系s[i]==s[j]
此时,dp[i][j]=dp[i+1][j-1]+2
- 为什么是+2呢?因为本题是最长回文子序列,当
s[i]==s[j]
时,[i,j]
范围内至少有dp[i+1][j-1]+2
这个大小的最长回文子序列,+2就是加上s[i],s[j]
这两个字符。
- 如果
s[i]与s[j]不相同
,说明s[i]和s[j]
的同时加入 并不能增加[i,j]
区间回文子序列的长度,那么分别加入s[i]、s[j]
看看哪一个可以组成最长的回文子序列。
加入s[j]
的回文子序列长度为dp[i + 1] [j]
。
加入s[i]
的回文子序列长度为dp[i] [j - 1]
。
那么dp [i] [j]
一定是取最大的,即:dp [i] [j] = max(dp [i + 1] [j], dp[i] [j - 1])
;
3.如何初始化dp数组
- 首先,我们得处理特殊情况,当
i==j
的时候,这个时候在[i,j]
范围内只有一个字符,使用dp[i][j]=dp[i+1][j-1]+2
会导致当前处理的子串的左边界大于右边界,此时我们就得特殊处理一下,当处理的子串只有一个字符时,i==j
,并且dp[i][j]
显然等于1,因为单个字符也是回文子序列,并且这个回文子序列的长度是1。
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
4. 确定遍历顺序
从递归公式中,可以看出,dp[i][j]
依赖于 dp[i + 1][j - 1]
,dp[i + 1][j] 和 dp[i][j - 1]
,如图:
- 所以说我们想要得到
dp[i][j]
,必须从左下方开始,向着右上方的方向进行递推。 - 所以说遍历顺序就是从下到上,从左到右
//开始对dp数组进行从下到上,从左到右进行赋值。
for(int i=s.size()-1;i>=0;i--){
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(dp[i][j-1],dp[i+1][j]);
}
}
5.举例打印dp数组
输入s:"cbbd" 为例,dp数组状态如图:
红色框即:dp[0][s.size() - 1];
为最终结果。
最终代码:
//最长回文子序列
class Solution {
public:
int longestPalindromeSubseq(string s) {
//创建二维的dp数组
vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
//初始化dp数组,首先要将i和j相等的时候,也就是只有一个字符的子序列,它的dp值赋值为1
for(int i=0;i<s.size();i++) dp[i][i]=1;
//开始对dp数组进行从下到上,从左到右进行赋值。
for(int i=s.size()-1;i>=0;i--){
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(dp[i][j-1],dp[i+1][j]);
}
}
//最后,从0-s.size()-1这个范围的最长回文子序列的长度就是我们需要的答案。
return dp[0][s.size()-1];
}
};
注明
- 本文中引用了作者
代码随想录
的部分图片和原文,若想深入了解,可以去原作者的文章阅读 - 代码随想录
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”