【算法|动态规划No.29】leetcode132. 分割回文串 II

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
在这里插入图片描述

点击直接跳转到该题目

目录

  • 1️⃣题目描述
  • 2️⃣题目解析
  • 3️⃣解题代码

1️⃣题目描述

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例1:

输入:s = “aab”
输出:1
解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

示例2:

输入:s = “a”
输出:0

示例3:

输入:s = “ab”
输出:1

注意:

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

2️⃣题目解析

状态表示:

  • dp[i]表示区间[0,i]之间最长的子串的最少分割次数。

状态转移方程如下:
在这里插入图片描述

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];}
};

最后就顺利通过啦!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/166578.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue3+vite中使用Lottie动画

Lottie通过读取json文件信息实现动画效果 官方文档 Lottie官网 lottie库有众多动画 选择下载Lottie JSON到项目中 安装Lottie包 pnpm add lottie-web 模板创建 <template><div class"bg"><div id"canvas" class"canvas" ref&quo…

react antd实现upload上传文件前form校验,同时请求带data

最近的需求&#xff0c;两个下拉框是必填项&#xff0c;点击上传按钮&#xff0c;如果有下拉框没选要有提示&#xff0c;如图 如果直接使用antd的Upload组件&#xff0c;一点击文件选择的窗口就打开了&#xff0c;哪怕在Button里再加点击事件&#xff0c;也只是&#xff08;几乎…

MyBatisPlus实现连表操作、批量处理

1、实现连表查询 正常来说单靠mybatisplus无法实现连表查询&#xff0c;只能靠单表sql然后进行拼接形成连表查询&#xff0c;或者使用xml文件去编写sql语句来实现连表查询。但他又给我们提供了一个插件MyBatis-Plus-Join&#xff0c;用来弥补mybatisplus再连表上的不足&#…

那些你面试必须知道的webpack知识点

目录 1、webpack介绍和简单使用1.1 什么是webpack&#xff1f;1.2 安装webpack1.3 简单使用一下webpack 2、webpack的入口与输出2.1 入口(entry)2.2 输出(output) 3、入口多种配置方法3.1 多文件打包成一个文件3.2 多文件打包成多文件 4、loader的概念5、压缩打包HTML5.1 使用步…

用 pytorch 训练端对端验证码识别神经网络并进行 C++ 移植

文章目录 前言安装安装 pytorch安装 libtorch安装 opencv&#xff08;C&#xff09; 准备数据集获取训练数据下载标定 编码预分析 数据集封装格式 神经网络搭建神经网络训练神经网络测试神经网络预测C 移植模型转换通过跟踪转换为 Torch Script通过注解转换为 Torch Script 编写…

【工具】SecureCR-8.5下载、安装激活和使用教程

起初我参考的文章&#xff1a;【工具】SecureCR-8.5下载、安装激活和使用教程&#xff08;包含常用设置&#xff09;_securecrt激活_SecureCode的博客-CSDN博客 但是不行啊&#xff0c;执行到13步的时候报错&#xff1a; 问了作者也没有回应&#xff0c;直到我参考了&#xff…

神经网络的发展历史

神经网络的发展历史可以追溯到上世纪的数学理论和生物学研究。以下是神经网络发展史的详细概述&#xff1a; 1. 早期的神经元模型&#xff1a; 1943年&#xff0c;Warren McCulloch和Walter Pitts提出了一种神经元模型&#xff0c;被称为MCP神经元模型&#xff0c;它模拟了生…

车载视频如何转换视频格式

当你收集了多种视频想在车内进行播放&#xff0c;它们可能不会自动播放。你有可能会在屏幕上看到一条消息&#xff0c;显示“文件格式不受支持”&#xff0c;这是因为这些视频可能采用了你的汽车无法识别的格式。 那我们如何才可以转换为车载播放器上运行的最重要且最广泛使用…

Yakit工具篇:专项漏洞检测的配置和使用

简介&#xff08;来自官方文档&#xff09; 专项漏洞检测是针对特定应用程序或系统进行的安全漏洞扫描技术&#xff0c;旨在检测与该应用程序或系统相关的安全漏洞。 Yakit通过对常见的中间件、CMS、框架、组件进行总结、归纳&#xff0c;并针对这些组件对其常见的高危漏洞进…

IP协议(上)

目录 一、初步认识IP协议 二、认识IP地址 三、协议报头格式 1.报头和有效载荷分离 2.20字节的固定数据 四、网段划分 1.一个小例子 2.认识IP地址的划分 3.数据的传输过程 4.特殊的IP地址 5.通信运营商 &#xff08;1&#xff09;通信运营商的作用 &#xff08;2&a…

Spring Security认证架构介绍

在之前的Spring Security&#xff1a;总体架构中&#xff0c;我们讲到Spring Security整个架构是通过Bean容器和Servlet容器对过滤器的支持来实现的。我们将从过滤器出发介绍Spring Security的Servlet类型的认证架构。 1.AbstractAuthenticationProcessingFilter AbstractAut…

Day6力扣打卡

打卡记录 统计无向图中无法互相到达点对数&#xff08;并查集 / DFS&#xff09; 链接 并查集 思路&#xff1a;用并查集将连通区域的连在一起&#xff0c;再遍历所有点&#xff0c;用hash表存储不同连通块的元素个数&#xff0c;然后 乘积和 便是答案。 注意&#xff1a; /…

计算机视觉基础(5)——特征点及其描述子

前言 本文我们将学习到特征点及其描述子。在特征点检测中&#xff0c;我们将学习角点检测和SIFT关键点检测器&#xff0c;角点检测以哈里斯角点检测器为例进行说明&#xff0c;SIFT将从高斯拉普拉斯算子和高斯差分算子展开。在描述子部分&#xff0c;我们将分别学习SIFT描述子和…

水库大坝安全监测方案,筑牢水库安全防线!

方案背景 党的十九届五中全会提出&#xff1a;“统筹发展和安全、加快病险水库除险加固”&#xff1b;国务院常务会议明确“十四五”期间&#xff0c;水库除险加固和运行管护要消除存量隐患&#xff0c;实现常态化管理&#xff1b;到2025年前&#xff0c;完成新出现病险水库的…

UVM-什么是UVM方法学

概念简介 百度对UVM的解释如下&#xff1a; 通用验证方法学&#xff08;Universal Verification Methodology, UVM&#xff09;是一个以SystemVerilog类库为主体的验证平台开发框架&#xff0c;验证工程师可以利用其可重用组件构建具有标准化层次结构和接口的功能验证环境 UVM…

我国跨境电商行业研究报告(2022)

我国跨境电商行业研究报告 我国跨境电商规模突飞猛进&#xff0c;2022年进出口规模超2万亿元&#xff0c;2023年上半年跨境电商出口8210亿元&#xff0c;增长19.9%。全国跨境电商主体已超10万家&#xff0c;近年来涌现出一批上市公司&#xff0c;以及广州希音等全球独角兽企业。…

【了解一下,Elastic Search的检索】

文章目录 **1.1.ES**1.1.1.elasticsearch的作用**1.1.2.ELK栈****2.索引库操作****2.1.mapping映射属性****2.2.索引库的CRUD** **3. 文档操作** **基于IDEA操作ES****索引操作****文档操作** DSL查询文档**1.1.DSL查询分类****1.2. 全文检索查询****1.3. 精准查询****1.4. 地理…

淘宝商品详情API接口(标题|主图|SKU|价格|销量|库存..)

一、应用场景 淘宝商品详情接口的应用场景非常广泛&#xff0c;以下是其中几个例子&#xff1a; 商家用于展示商品信息&#xff1a;淘宝详情接口可以被用于商家的自主店铺或第三方电商平台上&#xff0c;方便展示商品详细信息。 商品价格比对&#xff1a;淘宝详情接口可以用于…

2.4 如何在FlinkSQL使用DataGen(数据生成器)

1、DataGen SQL 连接器 FLinkSQL中可以使用内置的DataGen SQL 连接器来生成测试数据 官网链接&#xff1a;DataGen SQL 连接器 2、随机数数据生成器 随机数数据生成器支持随机生成 char、varchar、binary、varbinary、string 类型的数据 它是一个无界流的数据生成器 -- TO…