博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode 516. Longest Palindromic Subsequence 解题报告
阅读量:2359 次
发布时间:2019-05-10

本文共 2675 字,大约阅读时间需要 8 分钟。

LeetCode 516. Longest Palindromic Subsequence 解题报告

题目描述

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000..


示例

Example 1:

Input : “bbbab”
Output : 4
One possible longest palindromic subsequence is “bbbb”.

Example 2:

Input : “cbbd”
Output : 2
One possible longest palindromic subsequence is “bb”.


注意事项

没有给出.


解题思路

我的思路:

这道题考的是最长回文子序列,注意是序列而不是子串,序列的意思是组成回文的字符可以是不连续的,而回文子串则需要连续的,比如例子中的bbbab,最长回文序列是bbbb,最长回文子串是bbb或是bab。

当已知一个序列是回文时,添加首尾元素后的序列存在两种情况,一种是首尾元素相等,则最长回文的长度加2,当首尾元素不相等,则最长回文序列为仅添加首元素时的最长回文与仅添加尾元素时的最长回文之间的最大值。我们可以用dp[i][j]表示s[i…j]中的最长回文序列,而状态转移方程则是

1. i > j,dp[i][j] = 0;
2. i == j,dp[i][j] = 1;
3. i < j且s[i] == s[j],dp[i][j] = dp[i + 1][j - 1] + 2;
4. i < j且s[i]!= s[j],dp[i][j] = max(dp[i + 1][j],dp[i][j - 1]);

从状态转移方程可以看出,计算dp[i][j]时需要用到dp[i+1][j - 1]和dp[i + 1][j],所以对于i的遍历应该从尾部开始,最后返回dp[0][s.length() - 1]就行。见下面我的代码1。

改进思路:

上述的算法时间复杂度是 O(n2) ,空间复杂度是 O(n2) 。然而从状态转移方程来看,计算dp[i][x]时,只用到了dp[i][y]和dp[i + 1][z],即计算当前行时,只用到了当前行和下一行,因此可以对上一个算法进行改进,需要用两行空间存储就能完成计算。

用一个变量cur表示当前行的下标,cur的取值为0或1,1 - cur表示的就是另外一行,因此状态转移方程变成了:

1. i > j,dp[cur][j] = 0;
2. i == j,dp[cur][j] = 1;
3. i < j且s[i] == s[j],dp[cur][j] = dp[1 - cur][j - 1] + 2;
4. i < j且s[i]!= s[j],dp[cur][j] = max(dp[1 - cur][j],dp[cur][j - 1]);
注意每次计算完一个i后需要更新cur的值,即cur = 1 - cur。因为循环执行最后一次之后会多更新一次cur,所以返回的是dp[1 - cur][s.length() - 1]的值。见下面我的代码2。


代码

我的代码1:

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

我的代码2:

class Solution {public:    int longestPalindromeSubseq(string s) {        int n = s.length(), cur = 0;        vector
> dp(2, vector
(n, 0)); for (int i = n - 1; i >= 0; i--) { dp[cur][i] = 1; for (int j = i + 1; j < n; j++) { if (s[i] == s[j]) { dp[cur][j] = dp[1 - cur][j - 1] + 2; } else { dp[cur][j] = max(dp[1 - cur][j], dp[cur][j - 1]); } } cur = 1 - cur; } return dp[1 - cur][n - 1]; }};

总结

回文类的题目是动态规划蛮经典的问题,需要区分问的是回文序列还是回文子串,利用好回文的性质,想出状态转移方程就能得出结果,关键还是多写,接触多了就能熟悉应该怎样去解决。

由于做的刚好是回文的问题,作为对比,下周会做一道最长回文子串问题,求解最长回文子串除了动态规划,还有另外一种更巧妙的算法,下周再详细解释,努力加油~

转载地址:http://iqntb.baihongyu.com/

你可能感兴趣的文章
关于最小生成树的Prim算法和Kruskal算法
查看>>
Jenkins+Maven+SVN自动部署配置文档
查看>>
jenkins的安装配置,插件配置,安装插件,配置maven,jdk路径,配置安装插件,项目配置,自动构建配置
查看>>
redis集群启动脚本
查看>>
spring-session使用配置(分布式共享session配置)
查看>>
深入理解 Spring 事务原理
查看>>
单点登录原理与简单实现
查看>>
通俗理解ZooKeeper是如何保证数据一致性的
查看>>
Zookeeper核心工作机制(zookeeper特性、zookeeper数据结构、节点类型)
查看>>
基于Zookeeper的分布式锁
查看>>
程序员想提升工作效率,就别再做这七件事啦
查看>>
微信2015 年最热门的 10 篇技术文章,共 100 多篇精华
查看>>
程序员必须知道的10大基础实用算法及其讲解
查看>>
C/C++内存泄漏及检测
查看>>
nginx安装过程记录
查看>>
em单位的理解和使用
查看>>
localStorage的理解和应用
查看>>
base64图片编码大小与原图文件大小之间的联系
查看>>
安装和认识express框架
查看>>
三种主流的JVM(JDK)使用心得
查看>>