首页 > 其他分享 >动态规划-回文串问题——132.分割回文串II

动态规划-回文串问题——132.分割回文串II

时间:2024-11-01 21:20:47浏览次数:5  
标签:isPal int 分割 II 132 字符串 dp 回文

1.题目解析

题目来源:132.分割回文串II——力扣

测试用例

2.算法原理

首先回文串问题一定首先需要保存每个回文子串出现的位置,即二维dp表来存储所有子字符串中符合回文子串的位置,如图

1.状态表示

创建一个一维dp表来存储第i个位置之前的字符串数组全部划分为回文子串需要切的最小分割次数

即dp[i]:以第i个位置为结尾的子字符串全部划分为子字符串所需要分割的最小次数

2.状态转移方程

当[0,i]位置的字符串是回文子串时就不用分割,因此dp[i]=0,反之需要创建新的指针j(1<=j <=i)在[1,i]之间寻找(因为单个字符一定是回文子串所以第一个字符无需判断,这里j就直接从1开始遍历),当[j,i]区间的字符串是回文子串时就需要更新最小分割数,即dp[i]=min(dp[i],dp[j-1]+1)

3.初始化

因为需要求最小分割数,所以求min值时为了原来未填写的dp表中的数字不干扰,就可以将dp表初始化为INT_MAX

4.填表顺序

从左到右依次填写

5.返回值 

返回最后一个位置dp表的值

3.实战代码

代码分析 

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j]) {
                    isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;
                }
            }
        }
        vector<int> dp(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            if (isPal[0][i]) {
                dp[i] = 0;
            } else {
                for (int j = 1; j <= i; j++) {
                    if (isPal[j][i]) {
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }
};

标签:isPal,int,分割,II,132,字符串,dp,回文
From: https://blog.csdn.net/2301_80689220/article/details/143440292

相关文章

  • [小语言模型-代码生成]Textbooks Are All You Need II: phi-1.5 technical report
    全文总结本文介绍了phi-1.5技术报告,探讨了更小的Transformer基语言模型的能力。研究背景背景介绍:这篇文章的研究背景是近年来大型语言模型(LLMs)在自然语言处理领域的显著进步,特别是像GPT-4这样的最新一代模型展示了前所未有的能力。然而,这些模型的规模也带来了巨大的经济......
  • UcOs-III 源码阅读: os_flag.c
    /***********************************************************************************************************uC/OS-III*TheReal-TimeKernel**Copy......
  • 基于IIR数字滤波器的设计matlab毕业设计
    引言MATLAB是矩阵实验室(MatrixLaboratory)的简称,是美国MathWorks公司出品的商业数学软件,用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境,主要包括MATLAB和Simulink两大部分。MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应......
  • NiosII+GPS/GSM实现汽车状态监控系统
    基于SoPC的汽车安全监控系统采用Altera公司最新的SoPC(可编程片上系统)解决方案——Nios处理器软核为核心,配合GPS和GSM系统,对汽车的停放和运行状态进行监控。基于SoPC的汽车安全监控系统可广泛应用于汽车的防盗、日常维护和交通事故的处理,为车辆故障提供有效的测试手段。......
  • IIS 部署 .NET8/7/6/5
    以我公司所在的测试服务器为例:windowsserver2012、IIS7部署.NET8程序不出意外会报这个错:ThespecifiedversionofMicrosoft.NetCore.ApporMicrosoft.AspNetCore.Appwasnotfound.这是因为服务器没有安装HostingBundle在安装完HostingBundle之后,可能还会报如下......
  • UcOs-III 源码阅读: os_mem.c
    //作用:固定大小内存管理器的代码,内存分区代码/***********************************************************************************************************uC/OS-III*TheReal......
  • UcOs-III 源码阅读: os_mutex.c
    //作用:管理互斥量的代码/***********************************************************************************************************uC/OS-III*TheReal-TimeKernel**......
  • Windows11系统iisetw.dll文件丢失问题
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个iisetw.dll文件(挑选合适的版本文件)把它放......
  • UcOs-III 源码阅读: os_stat.c
    //作用:包含统计任务的代码,用来计算全局CPU使用率以及每个任务的CPU使用率;/***********************************************************************************************************uC/OS-III*......