516.longest-palindromic-subsequence.md

题目地址(516. 最长回文子序列)

https://leetcode-cn.com/problems/longest-palindromic-subsequence/

题目描述

 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。 示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。 示例 2: 输入: "cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。 提示： 1 <= s.length <= 1000 s 只包含小写英文字母 

前置知识

• 动态规划

公司

• 阿里
• 腾讯
• 百度
• 字节

思路

这是一道最长回文的题目，要我们求出给定字符串的最大回文子序列。

解决这类问题的核心思想就是两个字“延伸”，具体来说

• 如果一个字符串是回文串，那么在它左右分别加上一个相同的字符，那么它一定还是一个回文串，因此回文长度增加2
• 如果一个字符串不是回文串，或者在回文串左右分别加不同的字符，得到的一定不是回文串,因此回文长度不变，我们取[i][j-1]和[i+1][j]的较大值

事实上，上面的分析已经建立了大问题和小问题之间的关联， 基于此，我们可以建立动态规划模型。

我们可以用 dp[i][j] 表示 s 中从 i 到 j（包括 i 和 j）的回文序列长度， 状态转移方程只是将上面的描述转化为代码即可：

if(s[i]===s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);}

base case 就是一个字符（轴对称点是本身）

关键点

• ”延伸“（extend）

代码

代码支持：JS，Python3

JS Code：

/* * @lc app=leetcode id=516 lang=javascript * * [516] Longest Palindromic Subsequence *//** * @param {string} s * @return {number} */varlongestPalindromeSubseq=function(s){// bbbab 返回4// tag : dpconstdp=[];for(leti=s.length-1;i>=0;i--){dp[i]=Array(s.length).fill(0);for(letj=i;j<s.length;j++){if(i-j===0)dp[i][j]=1;elseif(s[i]===s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);}}}returndp[0][s.length-1];};

Python3 Code（记忆化递归）：

classSolution: deflongestPalindromeSubseq(self, s: str) ->int: @cachedefdp(l,r): ifl>=r: returnint(l==r) ifs[l] ==s[r]: return2+dp(l+1,r-1) returnmax(dp(l+1, r), dp(l, r-1)) returndp(0, len(s)-1)

Python3 Code(普通 dp)

classSolution: deflongestPalindromeSubseq(self, s: str) ->int: n=len(s) dp= [[0]*nfor_inrange(n)] foriinrange(n-1, -1, -1): forjinrange(i, n): ifi==j: dp[i][j] =1elifs[i] ==s[j]: dp[i][j] =dp[i+1][j-1]+2else: dp[i][j] =max(dp[i+1][j], dp[i][j-1]) returndp[0][-1] 

复杂度分析

• 时间复杂度：枚举所有的状态需要 n^2 时间，状态转移需要常数的时间，因此总的时间复杂度为 $O(n^2)$
• 空间复杂度：我们使用二维 dp 存储所有状态，因此空间复杂度为 $O(n^2)$

相关题目

• 5.longest-palindromic-substring

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。