首页 > 其他分享 >第九章 动态规划Part13

第九章 动态规划Part13

时间:2024-09-01 11:47:37浏览次数:11  
标签:子串 第九章 Part13 len range 序列 动态 dp 回文

目录

任务

647. 回文子串

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

思路

这道题的DP思路不是很直观,dp表示的不是某区间的回文子串数目,dp[i][j]表示[i,j]是否是回文子串,如果是则加结果加一,遍历完整个区间后,得到整个区间每个子区间各种情况的回文子串,累加起来即是所求。
那么只有s[i] == s[j]时,区间长度为1 和为2时,直接赋True,区间长度大于2时,如果 dp[i+1][j-1] 为True,则dp[i][j]为True
注意初始化和遍历顺序

class Solution:
    def countSubstrings(self, s: str) -> int:
        #dp[i][j]表示[i,j]是否是回文子串
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i] == s[j]:
                    if j-i <= 1: 
                        dp[i][j] = True
                        result += 1
                    elif dp[i+1][j-1]:
                        dp[i][j] = True
                        result += 1
        return result

516. 最长回文子序列

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

思路

该题比上题直观很多,dp[i][j]表示[i,j]范围内的最长回文子序列长度。s[i] == s[j]时,长度拓展2;不相等时,长度取dp[i+1][j]和dp[i][j-1]的最大值(因为不等时说明两边不能同时加入,就取一边加入后的最大值)。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        #dp[i][j]表示[i,j]范围内的最长回文子序列长度
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)): # i==j时表示单元素区间,此时为最长回文子序列长度为1
            dp[i][i] = 1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                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][len(s)-1]    

标签:子串,第九章,Part13,len,range,序列,动态,dp,回文
From: https://www.cnblogs.com/haohaoscnblogs/p/18391155

相关文章

  • 算法设计与分析:实验四 动态规划—鸡蛋掉落问题
    实验内容:动态规划将问题划分为更小的子问题,通过子问题的最优解来重构原问题的最优解。动态规划中的子问题的最优解存储在一些数据结构中,这样我们就不必在再次需要时重新处理它们。任何重复调用相同输入的递归解决方案,我们都可以使用动态规划对其进行优化。鸡蛋掉落问题是理解......
  • 第146篇:响应式动态居中(js+css,vue)
    好家伙, 1.使用js原生<divid="container"style="position:relative;width:100%;height:100vh;"><divid="hero"style="position:relative;"></div></div><script>consthero=doc......
  • 动态链接库的生成和使用(二)
    1、编写源文件和头文件Demo目录下创建testso文件夹,在下面创建test.cpp、test.h和Makefile文件test.cpp:#include<stdio.h>#include<stdlib.h>extern"C"doublecalc_pi(){ doublex=0; doubley=0; doublepi=0; intnum=0; intiter=0; constinttry_t......
  • jenkins动态切换环境
    一.代码层实现动态切换1.首先在conftest.py下声明pytest_addoption钩子函数,写法如下defpytest_addoption(parser):#设置要接收的命令行参数parser.addoption("--env",default="prod",choices=['pre','uat','prod','test'],......
  • lambdaQueryWrapper及动态获取字段名
    实体对象importcom.baomidou.mybatisplus.annotation.TableField;importlombok.Data;@Data@Table("")publicclassUser{privateLongid;@TableField("t_name")privateStringname;@TableField("t_age")priv......
  • 动态规划 之《从入门到入土》
    bushi动态规划的几个模板and例题背包问题01背包顾名思义,一个东西只有选和不选两种选择。求体积一定的包里能放的最大质量。 for(inti=1;i<=n;i++) { for(intj=m;j>=w[i];j--)//w[i]表示物品i的体积 { f[j]=max(f[j],f[j-w[i]]+v[i]);//v[i]表示物品i的质......
  • CSS、JS之动态展开式菜单
    效果演示实现了一个可展开菜单按钮的效果,点击按钮会弹出一个菜单列表,菜单列表中包含多个选项。按钮的样式为一个圆形背景,中间有三条横线,表示可以展开。当按钮被点击后,三条横线会变成一个叉号,表示可以收起。菜单列表的样式为一个白色背景,四周有阴影,包含多个选项,每个选项都有......
  • 第九章 动态规划Part12
    目录任务115.不同的子序列思路583.两个字符串的删除操作思路72.编辑距离思路任务115.不同的子序列给你两个字符串s和t,统计并返回在s的子序列中t出现的个数,结果需要对10^9+7取模。思路dp[i][j]表示s[0:i)中出现以t[0,j)的次数每次拓展一个字符,求次数,直到拓......
  • JS动态引入模块
    这是静态引入,importxxfrom‘xxx’;这是动态引入,import('xxx')动态引入是一个异步操作,即它会返回一个Promise对象,因此我们可以捕获引入失败的异常。具体运用场景:路由由后端动态生成,前端根据获取到的路由动态生成菜单,并根据对应路由去找到对应的组件进行跳转。譬如路由为/hom......
  • 实现一个动态评论系统:Vue3与后端API交互
    在当今的开发环境中,评论系统是多种应用中不可或缺的一部分,本文将带您深入了解如何使用Vue3实现一个动态评论系统,并与后端API进行交互。我们将重点使用Vue3的compositionAPI(setup语法糖)来构建这个系统。需求概述在构建动态评论系统时,我们需要实现以下功能:获取评论......