[leetcode]516_最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成

---

解题思路：【动态规划】

dp[i][j]：表示区间范围[i,j]的最长回文序列数；初始化为0当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况情况一：下标i 与 j相同，同一个字符例如a，dp[i][j] = 1情况二：下标i 与 j相差为1，例如aa, dp[i][j] = 2或者 dp[i][j] = dp[i + 1][j - 1] + 2;数组所有初始化为0，相差1时，dp[i + 1][j - 1] = 0情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间最长回文序列数取决于aba中的回文序列数，那么aba的区间就是 i+1 与 j-1区间，即dp[i][j] = dp[i + 1][j - 1] + 2

可参考博文：[leetcode]647_回文子串-CSDN博客

class Solution:"""dp[i][j]: 从i 到 j的最长回文子序列数"""def max_palindrome_list_dp(self,s):length = len(s)dp = [[0]*length for _ in range(length)]for i in range(length - 1, -1, -1):for j in range(i, length):if s[i] == s[j]:if i - j == 0:dp[i][j] = 1else:dp[i][j] = dp[i + 1][j - 1] + 2else:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])return dp[0][-1]if __name__ == '__main__':s = input()result_s = Solution().max_palindrome_list_dp(s)print(result_s)

---

仅作为代码记录，方便自学自查自纠