首页 > 其他分享 >线性DP-2472. 不重叠回文子字符串的最大数目

线性DP-2472. 不重叠回文子字符串的最大数目

时间:2022-11-15 23:24:38浏览次数:45  
标签:2472 extend flag range DP 字符串 dp 回文

问题描述

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串:

每个子字符串的长度 至少 为 k 。
每个子字符串是一个 回文串 。
返回最优方案中能选择的子字符串的 最大 数目。

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

示例 1 :

输入:s = "abaccdbbd", k = 3
输出:2
解释:可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文,且长度至少为 k = 3 。
可以证明,无法选出两个以上的有效子字符串。
示例 2 :

输入:s = "adbcda", k = 2
输出:0
解释:字符串中不存在长度至少为 2 的回文子字符串。

提示:

1 <= k <= s.length <= 2000
s 仅由小写英文字母组成

问题求解

典型的线性dp,dp[i]表示以i-1结尾的最大数目,判断一下是否包含最后一个字符即可。
另外加入一个判断所有回文子串的模块。

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        flag = [[0] * n for _ in range(n)]
        
        def extend(s, l, r):
            if l < 0 or r >= n or s[l] != s[r]: return
            flag[l][r] = 1
            extend(s, l - 1, r + 1)

        for i in range(n):
            extend(s, i, i)
            extend(s, i, i + 1)
        
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i - 1]
            for j in range(i - k, -1, -1):
                if flag[j][i - 1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp[n]

标签:2472,extend,flag,range,DP,字符串,dp,回文
From: https://www.cnblogs.com/hyserendipity/p/16894425.html

相关文章

  • DP问题
    题目链接题目描述:妈妈成功将小竹救了出来,她觉得小竹实在是太笨了,决定关小竹一周禁闭。可是小竹哪里能忍受失去自由,他早就偷藏了一部手机用于联系你,请求你帮助他逃离。你......
  • python 线程池 ThreadPoolExecutor
    从Python3.2开始,标准库为我们提供了concurrent.futures模块,它提供了ThreadPoolExecutor(线程池)和ProcessPoolExecutor(进程池)两个类。相比threading等模块,该模......
  • 基于MATLAB的LDPC编译码仿真,调制为64QAM
    部分源码:%首先加载G,HclearallloadG.mat;loadH.mat;max_iter=50;L_frame=size(G,1);n_frame=100;start=0;step=2;finish=12;r=size(G,1)/size(G,2);M=6;Es=42;%......
  • dp状态设计
    迎接仪式题目描述LHX教主要来X市指导OI学习工作了。为了迎接教主,在一条道路旁,一群“Orz教主er”穿着文化衫站在道路两旁迎接教主,每件文化衫上都印着大字。一旁的......
  • XIicPs_MasterSendPolled和XIicPs_MasterRecvPolled
    Xilinx FPGA的IIC程序中的XIicPs_MasterSendPolled和XIicPs_MasterRecvPolled函数的使用,8位寄存器地址写入24位数据硬件平台:黑金AX7010开发板vivado版本:Vivado2017.4SDK......
  • 记录一个dpdk17版本在centos上编译时出现的bug及解决方法
    1、首先说明一下编译环境及bug现象:编译环境是centos7的系统,笔者的该环境上有两个版本的内核,如下。编译的dpdk版本为17.01版本(版本比较旧)。   之前使用的centos内核......
  • 界面控件DevExpress WPF拥有丰富SVG图像库,更好支持高DPI显示器
    DevExpressWPF拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专......
  • 经典dp::三角形求最大值
    洛谷1216思路求和最大,划分没子问题,求的每次子问题最大代码#include<iostream>#include<vector>usingnamespacestd;constintN=1010;intdp[N][N]={0};int......
  • 2022CCPC威海站 D - Sternhalma // 状压dp + 记忆化搜索
    题目来源:2022ChinaCollegiateProgrammingContestWeihaiSiteD-Sternhalma题目链接:https://codeforces.com/gym/104023/problem/D题意在一个\(19\)个格子的六边......
  • 【重识云原生】第四章云网络4.7.4节vhost-user方案——virtio的DPDK卸载方案
     《重识云原生系列》专题索引: 第一章——不谋全局不足以谋一域第二章计算第1节——计算虚拟化技术总述第三章云存储第1节——分布式云存储总述第四章云网络第一节——......