【动态规划】回文串问题
文章目录
- 动态规划(回文串问题)
- 1. 回文子串
- 2. 最长回文子串
- 3. 回文串分割 IV
- 4. 分割回文串 ||
- 5. 最长回文子序列
- 6. 让字符串成为回文串的最小插入次数
动态规划(回文串问题)
1. 回文子串
题目链接
-
状态表示
f[i][j]表示 i 到 j 的子串当中是否是回文 -
状态转移方程

-
初始化
最初所有的内容都是0即可
-
填表
因为 i j 需要用 i + 1 来初始化,所以这个时候需要从下往上填表
-
返回值
返回整个dp 表里true 的数目就可以
AC代码:
class Solution
{
public:int countSubstrings(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n));int ret = 0;for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]){dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;}if (dp[i][j]) ret++;}}return ret;}
};
2. 最长回文子串
题目链接
如果需要求一个字符串当中的最长的回文子串,需要将所有的回文子串找到,然后再所有的回文子串里面找打一个最长的就可以了
可以参考上一个题目回文子串
AC代码:
class Solution
{
public:string longestPalindrome(string s) {// 找到所有的回文子串int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n));int begin = 0, len = 1;for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]){dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;}if (dp[i][j] && j - i + 1 > len){begin = i;len = j - i + 1;}}}return s.substr(begin, len);}
};
3. 回文串分割 IV
题目链接
分析:如果暴力解题的话,i 和 j 可以把整个字符串分为3份,只需要遍历所有可能分为3份的情况直接判断是否都是回文串不就可以了。但是判断回文串需要花费时间,可以使用上面两道题的方法来判断是不是回文串
AC代码:
class Solution
{
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n));for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;}}for (int i = 1; i < n - 1; i++){for (int j = i; j < n - 1; j++){if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;}}return false;}
};
4. 分割回文串 ||
题目链接
-
状态表示
dp[i]表示0 到 i 之间,可以把所有子串都分割为回文串的最小次数 -
状态转移方程

-
初始化
所需初始位最大即可
-
填表
从左到右
-
返回值
AC代码:
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];}
};
5. 最长回文子序列
题目链接
-
状态表示
之前以某个位置为结尾来分析状态表示,如果dp[i]表示到i位置的最长回文子序列的长度来推导状态转移方程,只有长度是分析不出来状态转移方程。
dp[i][j]表示i j 这个区间内,最长的回文子序列的长度 -
状态转移方程

-
初始化
无需初始化
-
填表
因为需要用到 后面的值,所以填表需要从下到上,从左到右
-
返回值
AC代码:
class Solution
{
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]){dp[i][j] = i ==j ? 1 : dp[i + 1][j - 1] + 2;}else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}return dp[0][n - 1];}
};
6. 让字符串成为回文串的最小插入次数
题目链接
-
状态表示
dp[i][j]表示:i 到 j 这个区间内,成为回文串的最小插入次数 -
状态转移方程

-
初始化
-
填表
从下往上,从左到右
-
返回值
AC代码:
class Solution
{
public:int minInsertions(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : 0;else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;}}return dp[0][n - 1];}
};
相关文章:
【动态规划】回文串问题
文章目录 动态规划(回文串问题)1. 回文子串2. 最长回文子串3. 回文串分割 IV4. 分割回文串 ||5. 最长回文子序列6. 让字符串成为回文串的最小插入次数 动态规划(回文串问题) 1. 回文子串 题目链接 状态表示 f[i][j]表示 i 到 j …...
Laravel Swift Mail发送带附件的邮件报错 “Swift_IoException The path cannot be empty“处理
先说下情况,就是我要做一个发送附件的邮件发送功能,结果,报错:The path cannot be empty。给我整的有点迷糊,网上也没有类似的问题。后来,我检查了一下代码,发现有个地方,是需要给附…...
Linux下常见的代理服务器软件介绍
在Linux系统中,代理服务器是我们搭建网络环境和处理网络请求的常用工具。但是,你知道Linux下常见的代理服务器软件有哪些吗?本文将为你带来对几款常见的Linux代理服务器软件的介绍,帮助你选择适合的代理服务器。 一、Squid&#…...
SCSS的基本用法
1、声明变量 $ 声明变量的符号 $ 下面这张图左半部分是scss的语法,右半部分是编译后的css。(整篇文章皆是如此) 2、默认变量 !default sass 的默认变量仅需要在值后面加上 !default 即可。 如果分配给变量的值后面添加了 !default 标志…...
alertmanager创建nginx-ingress basic auth鉴权
步骤 生成密码 printf "admin:$(openssl passwd -crypt xxxxxx)\n" >> auth 创建新的 Kubernetes 密钥 kubectl create secret generic basic-auth --from-file auth -n victoria-metrics 修改 ingress 以使用 secret 中的凭证来实现基本身份验证 编辑 P…...
系列六、Redis中的五大数据类型及相关操作
一、五大数据类型 String类型、List类型、Set类型、ZSet类型、hash类型。 二、String类型 2.1、内存储存模型 2.2、常用操作命令 三、List类型 3.1、概述 list列表,相当于Java中的list集合。特点:元素有序 且 可以重复。 3.2、内存存储模型 3.3、常用…...
四大运营商的大流量卡测评,看完您会选哪个运营商?
很多朋友都说网上的流量卡资费是真的便宜,但是小编认为资费便宜归便宜,但是运营商的小心思也有不少。 今天小编就带大家看一看三大运营商推出的正规流量卡都有哪些小心思? 首先,移动推出的线上大流量卡数量是最少的ÿ…...
Apache-Maven
安装Maven 解压apache-maven到目录下 Maven目录如下 bin:目录中存放的是可执行文件,JAVA项目中的编译执行打包都要使用bin. conf:存放的是Maven的配置文件,本地配置、私服配置都需要在conf下的settings.xml进行配置。 lib下存放的是Maven所…...
什么是原子交换?
安全地在各个区块链网络之间传输资产对于释放被困流动性并吸引更多用户进入这一领域至关重要,同时也保持 Web3 的信任最小化核心价值。原子交换是一种让两个人在不依赖于中介来促成交易的情况下,在不同的区块链网络之间交换通证资产的方式。这为 DeFi 用…...
java springboot word文档转pdf
java springboot word文档转pdf 1、环境2、依赖3、代码 1、环境 1、java、springboot 2、maven或者gradle 3、办公软件(自己电脑上的wps或者office等,如果部署到服务器上也要安装,linux、Mac 都有,自己安装) 可能会遇…...
【Leetcode Sheet】Weekly Practice 2
Leetcode Test 1281 整数的各位积和之差(8.9) 给你一个整数 n,请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。 提示: 1 < n < 10^5 【原始代码】: int subtractProductAndSum(int n){//1 < n < 10^5//…...
【BERTopic应用 03/3】:微调参数
一、说明 一般来说,BERTopic 在开箱即用的模型中工作得很好。但是,当您有数百万个数据要处理时,使用基本模型处理数据可能需要一些时间。在这篇文章中,我将向您展示如何微调BERTopic中的一些参数并比较它们的结果。让我们潜入。 二…...
2023年上半年数学建模竞赛题目汇总与难度分析
2023年上半年数学建模竞赛题目汇总与难度分析 由于近年来国赛ABC题出题方式漂浮不定,没有太大的定性,目前总体的命题方向为,由之前的单一模型问题变为数据分析评价优化或者预测类题目是B、C题的主要命题方向。为了更好地把握今年命题的主方…...
Linux下搭建java环境
文章目录 一,xshell链接linux二,linux安装jdk环境 一,xshell链接linux 这里用到的工具,VMware搭配CentOS7 64位Xshell5 操作之前确保,传输Xshell连接了虚拟机 打开Xshell,文件->新建 主机ip—>进入虚拟机,右键打开终端,输入命令:ifco…...
String、StringBuffer、StringBuilder三者的异同?
String字符串 不可变的字符序列在 jdk1.8,我们底层用 char [ ] 存储在 jdk 17,我们底层用 byte [ ] 存储 StringBuffer字符串缓冲区类 可变的字符序列,线程安全的(synchronized),效率低在 jdk1.8…...
htmlCSS-----弹性布局案例展示
目录 前言 效果展示 编辑 代码 思路分析 前言 上一期我们学习了弹性布局,那么这一期我们用弹性布局来写一个小案例,下面看代码(上一期链接html&CSS-----弹性布局_灰勒塔德的博客-CSDN博客) 效果展示 代码 html代码&am…...
Fiddler模拟请求发送和修改响应数据
fiddler模拟伪造请求 方法一:打断点模拟HTTP请求 1、浏览器页面填好内容后(不要操作提交),打开fiddler,设置请求前断点,点击菜单fiddler,”Rules”\”Automatic Breakpoints”\”Before Requests” 2、在…...
RH850从0搭建Autosar开发环境【23】- Davinci Configurator之DCM实操实现DID的读取写入
配置DID 一、Developer中创建SWC1.1 创建Application Component Type1.2 实例化Component二、在SWC中创建接口以及Runnable2.1 创建DID的Service Ports2.2 创建DID的Service Runnable三、在Configurator连接接口以及生成代码3.1 连接DCM与SWC3.2 生成RTE3.3 生成SWC的DID的模板…...
ChatGPT收录
VSCode插件-ChatGPT 多磨助手 多磨助手 (domore.run) Steamship Steamship 免费合集 免费chatGPT - Ant Design Pro 免费AI聊天室 (xyys.one)...
Nginx随笔
Nginx下载链接 安装命令: apt update apt install nginx 一、基础命令(Ubuntu) 1、在全局 nginx -t //检查Nginx的配置文件是否有错 systemctl start nginx //启动Nginx systemctl stop nginx //停止Nginx systemctl status nginx //查…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
