【LeetCode】094. 分割回文串II
文章目录
- 1. 解题思路
- 1.1 创建dp表
- 1.2 状态转移方程
- 1.3 提前求出所有子串是否是回文串
- 2. 整体代码
1. 解题思路
1.1 创建dp表
这道题我们使用动态规划的方法来解,首先创建一个大小为字符串长度的dp表。dp[i] 表示 s[0, i] 的字符串最小划分多少次可以全划分为回文串。
1.2 状态转移方程
求状态转移方程,我们要考虑两种情况。s[0, i] 的字符串是回文串和不是回文串的情况。
注意,这里假设我们已经知道了哪段字符串是不是回文串,至于是如何知道的后面会说。
- 如果s[0, i]是回文串,那么问题很简单,不用切割就行,即dp[i] = 0;
- 如果s[0, i]不是回文串,我们要新增一个变量 j ,j 的范围为 (0, i],这里说明一些j的边界情况,j 要大于0的原因是 j 为0的情况即不用分割s[0, i]的情况(即s[0, i]为回文串的情况),j 为 i 的情况即 s[0, i-1] 中找不到从0开始且为回文串的情况。用这个 j 变量,我们遍历 j 的情况,j 是小于等于 i 的,那么 dp[j-1] 的值我们是知道的。如果从 j 到 i 的字符串是回文串,那么我们就令 dp[i] = min(dp[i], dp[j - 1] + 1); 遍历所有 j 的情况,就能求出 dp[i] 的最小值了。

1.3 提前求出所有子串是否是回文串
这个我在之前的博客就已经讨论过了,具体可见这篇文章。
2. 整体代码

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;// 创建dp表,由于是求最小值,可以先将所有位置初始化为最大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];}
};
相关文章:
【LeetCode】094. 分割回文串II
文章目录 1. 解题思路1.1 创建dp表1.2 状态转移方程1.3 提前求出所有子串是否是回文串 2. 整体代码 1. 解题思路 1.1 创建dp表 这道题我们使用动态规划的方法来解,首先创建一个大小为字符串长度的dp表。dp[i] 表示 s[0, i] 的字符串最小划分多少次可以全划分为回文…...
CBCGPRibbon 添加背景图片
resource.h中声明资源的ID:ID_RIBBON_BACKIMAGE rc文件中添加png图片路径: ID_RIBBON_BACKIMAGE PNG DISCARDABLE "res\\bkribbon.png" 代码中添加下测: //添加背景图片 m_wndRibbonBar.SetBackgroundImage(ID_RIB…...
无涯教程-Perl - last 语句函数
当在循环内遇到 last 语句时,循环立即终止,程序控制在循环后的下一条语句处恢复。您可以为LABEL提供最后一个语句,其中LABEL是循环的标签。 last 语句可以在嵌套循环内使用,如果未指定LABEL,则该语句将适用于最近的循环…...
网络安全 Day13-Linux三剑客awk知识
Linux三剑客awk知识 1. awk 介绍2. awk 语法3. 练习 1. awk 介绍 awk 是一门语言, 也是一个命令,Linux 有三剑客命令: grep/sed/awk三剑客的特长 grep 过滤内容sed 取行awk 取列 2. awk 语法 取列 取第一列文件($1): awk {print $1} 文件指定分隔符为文件: awk -F "指…...
java讲解Spring Boot配置文件级别 相互覆盖关系 解决一方不愿意给数据库密码 一方不愿意给源码时 数据库配置问题
前面 我们讲过Spring Boot 修改临时变量的方式 但另一个场景 就是 我们 在本地开发环境 用的是一个配置 但如果项目经理上线 他想改这些配置 怎么弄呢 特别是数据库之类的配置 很多线上是不太一样的 那么 我们先看一个比较基本的方法 在配置文件的同目录下创建一个目录 叫 con…...
点击表格行高亮
css中三元表达式 :class"[activeIndex index ? color : , item]"点击行高亮 <div click"actvied(index)" :class"[activeIndex index ? color : , item]"v-for"(item, index) in tableData" :key"index">{{ item…...
基于粒子群优化算法的配电网光伏储能双层优化配置模型[IEEE33节点](选址定容)(Matlab代码实现)
目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Matlab代码、数据、讲解 💥1 概述 由于能源的日益匮乏,电力需求的不断增长等,配电网中分布式能源渗透率不断提高,且逐渐向主动配电网方…...
零代码爬虫平台SpiderFlow的安装
什么是 Spider Flow ? Spider Flow 是一个高度灵活可配置的爬虫平台,用户无需编写代码,以流程图的方式,即可实现爬虫。该工具支持多数据源、自动保存至数据库、任务监控、抓取 JS 动态渲染页面、插件扩展(OCR 识别、邮…...
Java 与其他编程语言:比较分析
Java 擅长可移植性和可靠性,Python 擅长通用性和简单性,JavaScript 擅长 Web 开发,C 擅长性能,Go 擅长效率。 在广阔的软件开发世界中,选择正确的编程语言对于任何项目的成功都至关重要。Java 是一种以其多功能性和可移…...
Linux性能分析工具介绍(二)--内存、进程、磁盘、IO分析
目录 一、引言 二、Linux性能分析工具介绍 ------>2.1、进程 ------>2.2、内存 ------>2.3、磁盘 ------>2.4、IO 一、引言 本章从内存、IO、进程的角度,分析linux系统的性能 二、Linux性能分析工具介绍 2.1、进程 2.1.1、top top命令可以动态查看进程…...
海外热门地区/国家常见主体证件示例
海外热门地区/国家常见主体证件示例(本页面内容较多,你可以通过CtrlF搜索) Overseas Popular Areas / Countries Examples of Common certificates (This page has more content, you can search by CtrlF) 中国香港…...
【阵列信号处理】空间匹配滤波器、锥形/非锥形最佳波束成形器、样本矩阵反演 (SMI) 研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
使用MPU6050计算方向盘角度
我给你们作了榜样、叫你们照着我向你们所作的去作。 ——【约翰福音13:15】 1.前言 前段时间接到一个项目需求:使用现有的陀螺仪MPU6050实现计算当前车辆的方向盘角度。 2.需求分析 MPU6050可获取三轴角速度和三轴加速度,并通过算法可以获得横滚角、…...
区块链实验室(13) - 在PBFT中节点的度与其流量的特征
前面若干实验说明了PBFT的耗时、流量与度的特征,见 区块链实验室(10) - 实例说明PBFT的共识过程, 区块链实验室(11) - PBFT耗时与流量特征, 区块链实验室(12) - 网络拓扑对PBFT共识流量的影响 同样的实验方案,在100个节点构成的无标度网络中完成100次交…...
C++——文件操作
一、文本文件 C中输入输出是通过流对象进行操作,对于文件来说写文件就是将内容从程序输出到文件,需要用到写文件流ofstream;而读文件就是将内容从文件输入到程序,需要用到读文件流ifstream;这两个文件流类都包含在头文…...
channel通道笔记
channel通道笔记 介绍 语法 1.一般使用make创建channel(常用) c : make(chan datatype),datatype是数据类型 2.直接显示声明,创建的值为空,一般没有太大意义 var c chan datatype 三种定义写法: 既可以收数据又可以发数据:chan datatype只可以收数据:chan <- datatype只可…...
无涯教程-Lua - 面向对象
面向对象编程(OOP)是现代编程时代中使用最广泛的编程技术之一。 OOP的特征 类(Class) - 类是用于创建对象的可扩展模板。 对象(Objects) - 它是类的实例,并为其分配了单独的内存空间。 继承(Inheritance) - 这是一个概…...
Java中的IOUtils是什么?
Java中的IOUtils是一个工具类,用于简化文件和流的操作。它提供了一些常用的方法,如复制文件、读取文件、写入文件等。 下面是一个简单的示例,演示如何使用IOUtils来复制文件: import org.apache.commons.io.FileUtils; import j…...
电源板(220V转3.3V)调试问题总
目录 现象: 问题可能的影响: 排查过程: 1.测试EC3,C2都在6V左右, 2.怀疑变压器的问题。 2.怀疑原边反馈控制芯片的问题。 3.怀疑后级电路的问题。 现象: 电源板输出3.28V输出正常。 但是测试前级电压…...
【webpack】一些零碎的知识点记录:eslint配置、source-map配置、devServer配置
文章目录 前言eslint安装配置设置规则 devtool设置js.map文件使用模式解释文件说明建议方案 devServer安装配置 前言 有些知识点不知道咋归类,就先暂时放在同一个文章里了。这里只记录配置方式,配置的东西是什么就不过多解释了,因为一般需要…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...
DAY 45 超大力王爱学Python
来自超大力王的友情提示:在用tensordoard的时候一定一定要用绝对位置,例如:tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾: tensorboard的发展历史和原理tens…...
