首页 > 其他分享 >[leetcode]516_最长回文子序列

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

时间:2024-09-29 18:54:58浏览次数:9  
标签:__ 最长 length 序列 516 leetcode dp 回文

给你一个字符串 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] = 1
                    else:
                        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][-1]

if __name__ == '__main__':
    s = input()
    result_s = Solution().max_palindrome_list_dp(s)
    print(result_s)

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

标签:__,最长,length,序列,516,leetcode,dp,回文
From: https://blog.csdn.net/weixin_45653183/article/details/142625631

相关文章

  • [leetcode]53_最大子数组(序列)和
    给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例:输入:[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大,为6。示例2:输入:nums=[1]输出:1示例3:输入:nums=[5,4,-1,7,8]输出:23提示:1<=......
  • 【LeetCode Hot 100】22. 括号生成
    题目描述要求生成所有“合法”的括号字符串,就首先需要弄清楚括号字符串的合法性定义,也就是说如果我们现在有一个由小括号组成的字符串,该如何判断其是否符合要求。此前做过判断括号串是否合法的题目,那道题目中一般在遍历过程中维护一个栈,因为每个后括号都需要在已经遍历的子串中找......
  • Leetcode 887. 鸡蛋掉落
    1.题目基本信息1.1.题目描述给你k枚相同的鸡蛋,并可以使用一栋从第1层到第n层共有n层楼的建筑。已知存在楼层f,满足0<=f<=n,任何从高于f的楼层落下的鸡蛋都会碎,从f楼层或比它低的楼层落下的鸡蛋都不会破。每次操作,你可以取一枚没有碎的鸡蛋并把它从任一楼层......
  • 基于Java&MYSQL&Android的商品比价软件设计与实现20516-计算机毕设定制原创选题推荐(附
                                                 目 录摘要1绪论1.1开发背景1.2研究现状1.3论文结构与章节安排2 商品比价软件APP系统分析2.1可行性分析2.2......
  • 力扣刷题——2516. 每种字符至少取 K 个
    一开始想的很简单,觉得在数组两端维护两个下标,用贪心的方法模拟取数字。classSolution{public:inttakeCharacters(strings,intk){intleft=0,right=s.size()-1;if(k==0)return0;intres=0;vector<int>......
  • 2516. 每种字符至少取 K 个
    给你一个由字符'a'、'b'、'c'组成的字符串s和一个非负整数k。每分钟,你可以选择取走s最左侧还是最右侧的那个字符。你必须取走每种字符至少k个,返回需要的最少分钟数;如果无法取到,则返回-1。示例1:输入:s="aabaaaacaabc",k=2输出:8解释:从s的左侧取三个......
  • (nice!!!)LeetCode 2286. 以组为单位订音乐会的门票(线段树)
    题目:2286.以组为单位订音乐会的门票思路:线段树做法。(线段树)acwing1265.数星星classBookMyShow{public: //结构体typedefstructNode{intmn=0;//最小空位编号longlongsum=0;//非空位置之和}node; //n,mintN,M;......
  • P5165 xtq的棋盘 题解
    这个题也可以用矩阵加速解决。先考虑70pts的做法,我们设\(f_i\)为从\(i\)位置到达\(0\)的期望步数,并尝试用\(f_n\)表示出所有\(f_i\)并利用\(f_0\)解出\(f_n\)然后回带即可。具体地,设\(f_i=a\timesf_n+b\),\(f_{i-1}=c\timesf_n+d\),则由于:\[f_i=pr......
  • leetcode74 搜索二维矩阵
    leetcode74搜索二维矩阵思路可以使用二叉搜索,首先先看标准的闭区间二叉搜索代码publicintqSearch(int[]a,intl,intr,inttarget){intmid=(l+r)/2;if(l>r)returnl;//终止条件,区间为空if(a[mid]==target)returnmid;elseif(a[mid]<target)retur......
  • Leetcode 1235. 规划兼职工作
    1.题目基本信息1.1.题目描述你打算利用空闲时间来做兼职工作赚些零花钱。这里有n份兼职工作,每份工作预计从startTime[i]开始到endTime[i]结束,报酬为profit[i]。给你一份兼职工作表,包含开始时间startTime,结束时间endTime和预计报酬profit三个数组,请你计算并返回可......