公司做哪个网站比较好,网站开发流程 图书,网络推广引流有哪些渠道,南宁商城网站建设给你一个字符串 s #xff0c;找出其中最长的回文子序列#xff0c;并返回该序列的长度。
子序列定义为#xff1a;不改变剩余字符顺序的情况下#xff0c;删除某些字符或者不删除任何字符形成的一个序列。示例 1#xff1a;
输入#xff1a;s bbbab
输出找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。示例 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相同同一个字符例如adp[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的区间就是 i1 与 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) 仅作为代码记录方便自学自查自纠
