【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安装配置 前言 有些知识点不知道咋归类,就先暂时放在同一个文章里了。这里只记录配置方式,配置的东西是什么就不过多解释了,因为一般需要…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
