DP：回文串模型

一、回文子串

. - 力扣（LeetCode）

 该题有3种解法

（1）中心扩展算法（在字符串章节有介绍）时间复杂度O（N^2）,空间复杂度O（1）

（2）马丁车算法（专门用来解决回文串问题，但是适用返回太窄）时间复杂度O（N）,空间复杂度O（N）

（3）动态规划（可以将所有回文信息都保存在dp表中）时间复杂度O（N^2）,空间复杂度O（N^2）

这边重点介绍动态规划的做法。

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]的子串是否是回文串（i<=j）只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

dp表中true的个数

class Solution {
public:int countSubstrings(string s) {//动态规划的做法int ret=0;//s[i]==s[j]  1、i==j  2、i+1==j  3、dp[i+1][j-1]?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]) ret+=dp[i][j]=i+1<j?dp[i+1][j-1]:true;return ret;}
};

 二、最长回文子串

. - 力扣（LeetCode）

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]的子串是否是回文串（i<=j）只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

dp表中为true以及长度最大的子串的起始位置和长度

class Solution {
public:string longestPalindrome(string s) {//动态规划的思想int begin=0,len=1;//帮助我们返回结果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;if(dp[i][j]&&len<j-i+1) {begin=i;len=j-i+1;}}  }return s.substr(begin,len);}
};

三、分割回文子串I

. - 力扣（LeetCode）

解法1：动归预处理+回溯

class Solution {
public://动归预处理+回溯vector<vector<bool>> dp;//dp预处理vector<vector<string>> ret;//记录返回的结果vector<string> path;//记录路径的结果int n;vector<vector<string>> partition(string s) {//dp预处理n=s.size();dp.resize(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;//将dp数组交给dfs去处理dfs(s,0);return ret;}void dfs(string&s,int i){if(i==n) {ret.push_back(path);return;}for(int j=i;j<n;++j)if(dp[i][j]){path.emplace_back(s.substr(i,j-i+1));dfs(s,j+1);path.pop_back();}}
};

 解法2：回溯+记忆化搜索

class Solution {
public:
//回溯+记忆化搜索vector<vector<int>> f;//记忆化数组  0表示未搜索，1表示回文，-1表示不回文vector<vector<string>> ret;//记录返回的结果vector<string> path;//记录路径的结果int n;vector<vector<string>> partition(string s) {n=s.size();f.resize(n,vector<int>(n));//交给dfs帮助我们解决dfs(s,0);return ret;}void dfs(const string&s,int i){if(i==n) {ret.emplace_back(path);return;}for(int j=i;j<n;++j)if(ispal(s,i,j)){path.emplace_back(s.substr(i,j-i+1));dfs(s,j+1);path.pop_back();}}bool ispal(const string&s,int i,int j) //判断i->j是否回文{//先看看备忘录if(f[i][j]) return f[i][j];if(s[i]!=s[j]) return f[i][j]=false;else return f[i][j]=i+1<j?ispal(s,i+1,j-1):true;}
};

四、分割回文子串II

. - 力扣（LeetCode）

算法原理：

1、状态表示（经验+题目要求）

dp[i]表示s字符串[0，i]区间上的最长子串的最小分割次数

 2、状态转移方程

dp[i]:  

(1)0-i回文——>0

(2)0-i不是回文——>j-i是否回文——>min(dp[i],dp[j-1]+1)

3、初始化

都初始化为整型最大值，否则最后dp表里都是0会影响结果

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

dp[n-1]

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;elsefor(int j=1;j<=i;++j)//去看看左边 要怎么切割 左开右闭if(ispal[j][i]) dp[i]=min(dp[i],dp[j-1]+1);//j代表最后一个回文串的起始位置return dp[n-1];}
};

五、分割回文子串III（经典）

. - 力扣（LeetCode）

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示对于字符串的前i个字符，将他分割成j个子串，所需修改的最少字符数

 2、状态转移方程

int cost(string&s,int l,int r) 表示从s的i-j位置，变成回文串所需要的最小修改次数

dp[i][j]:  

(1)j==1（没有分割）  cost（s,0,i-1）

(2)j>1——>min(dp[i][j],dp[m][j-1]+cost(s,m,i-1))

3、初始化

初始化成INT_MAX 确保不影响最终结果 dp[0][0]=0 确保不影响结果

4、填表顺序

上到下，左到右

5、返回值

dp[n][k]

class Solution {
public:int palindromePartition(string s, int k) {//dp[i][j]表示对于字符串的前i个字符，将他分割成j个子串，所需修改的最少字符数int n=s.size();vector<vector<int>> dp(n+1,vector<int>(k+1,INT_MAX));dp[0][0]=0;for(int i=1;i<=n;++i)for(int j=1;j<=min(k,i);++j)if(j==1) dp[i][j]=cost(s,0,i-1);else for(int m=j-1;m<i;++m) dp[i][j]=min(dp[i][j],dp[m][j-1]+cost(s,m,i-1));//找前面的状态 0->i  分成j个//dp0->m+ cost m->ireturn dp[n][k];//0->n  k}int cost(string&s,int l,int r){int ret=0;for(int i=l,j=r;i<j;++i,--j)if(s[i]!=s[j]) ++ret;//需要修改一个才能成为回文return ret;}
};

六、分割回文串IV

 . - 力扣（LeetCode）

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]的子串是否是回文串（i<=j）只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

第二次枚举，先固定第一个位置，然后固定第二个位置，看看由两个位置分割出来的三个区域是否都为true

class Solution {
public:bool checkPartitioning(string s) {//将结果存到dp表中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;//第二次枚举 先固定第一个，然后固定第二个，然后看看3个是不是都是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;}
};

七、不重叠回文子字符串的最大数目

. - 力扣（LeetCode）

class Solution {
public:int maxPalindromes(string s, int k) {//dp[i]表示0->i中的不重叠回文子字符串的最大数目int n=s.size();vector<int> dp(n+1);//如果s[i]不在回文串中 dp[i+1]=dp[i]//如果s[r]在回文串中，采用中心扩展，l->r是回文子串，且r-l+1>=k 有dp[i]=max(dp[i],dp[l-1]+1)for(int i=0;i<n*2-1;++i){//两边到中间不适合判断长度，应该从中间到两边int l=i/2,r=l+i%2; //中心扩展判断是否回文dp[l+1]=max(dp[l],dp[l+1]);for(;l>=0&&r<n&&s[l]==s[r];--l,++r)if(r-l+1>=k){dp[r+1]=max(dp[r+1],dp[l]+1);break;}}return dp[n];}
};

八、最长回文子序列

. - 力扣（LeetCode）

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){//dp[i][j]表示i-j区间内所有子序列中，最长回文子序列的长度dp[i][i]=1;for(int j=i+1;j<n;++j)if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2; //i+1=j的情况可以不用考虑 //虽然会出现用不到的格子，但是里面是0所以不会影响计算结果else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}return dp[0][n-1];}
};

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]所有子序列中的最长子序列的长度

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>max(dp[i,j-1],dp[i+1][j])

(2)s[i]==s[j]——>

      i==j  1

      i+1==j   2

      dp[i+1][j-1]+2

3、初始化

初始化为0  dp[i][i]=1

4、填表顺序

上到下，左到右

5、返回值

dp[0][n-1]

九、让字符串成为回文串的最小插入次数

. - 力扣（LeetCode）

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]子串，使他成为回文子串的最小插入次数

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>min(dp[i,j-1],dp[i+1][j])+1

(2)s[i]==s[j]——>

      i==j  0

      i+1==j   0

      dp[i+1][j-1]

3、初始化

初始化为0 

4、填表顺序

下往上，左到右

5、返回值

dp[0][n-1]

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+1;j<n;++j)if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];else dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;return dp[0][n-1];}
};

 

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

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

相关文章

GPU风扇不旋转：为什么会发生这种情况以及如何修复

GPU风扇不旋转：为什么会发生这种情况以及如何修复

GPU在处理数百万像素时往往会发热，因此冷却风扇静音可能会令人担忧，这是可以理解的！如果你注意到你的GPU风扇没有旋转，下面是如何评估是否存在真正的问题，以及如何解决问题。 风扇停止旋转可能是一个功能，而不是一个Bug 如果GPU没有用于密集任务或没有达到高温，则可以…
阅读更多...
GEE训练教程——如何确定几何形状的中心点坐标和相交的坐标

GEE训练教程——如何确定几何形状的中心点坐标和相交的坐标

简介 在GEE中&#xff0c;可以使用.geometry()方法来获取几何形状的中心点坐标和相交的坐标。 首先&#xff0c;使用.geometry()方法获取几何形状的几何信息&#xff0c;然后使用.centroid()方法获取几何形状的中心点坐标。示例代码如下&#xff1a; // 获取几何形状的中心点…
阅读更多...
idea编码问题：需要 ＜标识符＞ 非法的类型 、需要为 class、interface 或 enum 问题解决

idea编码问题：需要 ＜标识符＞ 非法的类型 、需要为 class、interface 或 enum 问题解决

目录 问题现象 问题解决 问题现象 今天在idea 使用中遇到的一个编码的问题就是&#xff0c;出现了这个&#xff1a; Error:(357, 28) java: /home/luya...........anageService.java:357: 需要 <标识符> Error:(357, 41) java: /home/luya............anageService.ja…
阅读更多...
QT C++ QTableWidget 表格合并 setSpan 简单例子

QT C++ QTableWidget 表格合并 setSpan 简单例子

这里说的合并指的是单元格&#xff0c;不是表头。span的意思是跨度、宽度、范围。 setSpan函数需要设定行、列、行跨几格&#xff0c;列跨几格。 //函数原型如下 void QTableView::setSpan(int row, i nt column, 、 int rowSpanCount,/*行跨过的格数*/ int columnSpanCount…
阅读更多...
全球自动化立体库(智能仓储)顶级玩家TOP20

全球自动化立体库(智能仓储)顶级玩家TOP20

导语 大家好&#xff0c;我是社长&#xff0c;老K。专注分享智能制造和智能仓储物流等内容。 新书《智能物流系统构成与技术实践》 The Logistics IQ 对自动化存储领域的顶级玩家进行了分析&#xff0c;并发布了一份排名列表。 这些公司在自动化需求日益增长的背景下&#xff0…
阅读更多...
【亚马逊云科技 CSDN 联合巨献】 「对话AI 构建者：从基础到应用的 LLM 全景培训」 限时免费！

【亚马逊云科技 CSDN 联合巨献】 「对话AI 构建者：从基础到应用的 LLM 全景培训」 限时免费！

&#x1f680;&#x1f31f;【亚马逊云科技 & CSDN 联合巨献】 &#x1f4da;「对话AI 构建者&#xff1a;从基础到应用的 LLM 全景培训」&#x1f525; 限时免费&#xff01; &#x1f4c6; 抓紧时间&#xff01;6月7日前注册&#xff0c;原价 399&#xff0c;现在仅需 0…
阅读更多...
Git发布正式

Git发布正式

一般我们开发都是在测试环境开发&#xff0c;开发完成后再发布到正式环境。 一.分支代码合并到主分支1.首先切换到自己的分支(比如分支叫&#xff1a;dev)git checkout dev2.把本地分支拉取下来git pull 或者 git pull origin dev3.切换到主分支mastergit checkout master4.更新…
阅读更多...
表达式求值的相关语法知识（C语言）

表达式求值的相关语法知识（C语言）

目录 整型提升 整型提升的意义 整型提升规则 整型提升实例 算术转换 赋值转换 操作符的属性 C语言的语法并不能保证表达式的执行路径唯一&#xff01;&#xff01;&#xff01; 问题表达式 整型提升 C的整型算术运算总是至少以缺省整型类型的精度来进行的。为了获得这…
阅读更多...
Docker安装、使用，容器化部署springboot项目

Docker安装、使用，容器化部署springboot项目

目录 一、使用官方安装脚本自动安装 二、Docker离线安装 1. 下载安装包 2. 解压 3.创建docker.service文件 4. 启动docker 三、docker常用命令 1. docker常用命令 2. docker镜像命令 3. docker镜像下载 4.docker镜像push到仓库 5. docker操作容器 6.docker …
阅读更多...
Xcode中给UIView在xib中添加可视化的属性

Xcode中给UIView在xib中添加可视化的属性

给UIView在xib中添加可视化的属性 效果如下图&#xff1a; 可以直接设置view 的 borderColor 、borderWidth、cornerRadius&#xff0c;也可以单独指定view的某个角是圆角。减少了代码中的属性。 完整代码&#xff1a; UIViewBorder.h #import <UIKit/UIKit.h>inter…
阅读更多...
jmeter并发测试

jmeter并发测试

目录 常用的压测工具jmeter安装配置并执行新建测试计划 Test Plan添加线程组练习01&#xff1a;共10个线程&#xff0c;每秒钟启动一个线程&#xff08;需要10秒&#xff09;&#xff0c;每个线程发送两个请求练习02&#xff1a;共10个线程&#xff0c;1秒中内启动完毕&#xf…
阅读更多...
系统思考—心智模式

系统思考—心智模式

凯恩斯说&#xff1a;“介绍新观念倒不是很难&#xff0c;难的是清除那些旧观念。”在过去的任何一年&#xff0c;如果你一次都没有推翻过自己最中意的想法&#xff0c;那么你这一年就算浪费了。旧观念像是根深蒂固的杂草&#xff0c;即使在新知识的光照下&#xff0c;也需要时…
阅读更多...
OpenFeign远程接口调用使用公共模块出现的错误

OpenFeign远程接口调用使用公共模块出现的错误

今天在使用openfeign和sentinel实现fallback服务降级时遇到找不到类型的异常 检查代码发现没有错误&#xff0c;EnableFeignClients也在启动类上标注了 错误信息&#xff1a;A component required a bean of type com.zxc.cloud.apis.PayFeignSentinelApi that could not be f…
阅读更多...
Mysql学习（七）——约束

Mysql学习（七）——约束

文章目录 四、约束4.1 概述4.2 约束演示4.3 外键约束 总结 四、约束 4.1 概述 概念&#xff1a;约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。目的&#xff1a;保证数据库中数据的正确、有效性和完整性。分类&#xff1a; 4.2 约束演示 根据需求&…
阅读更多...
opencv快速安装以及各种查看版本命令

opencv快速安装以及各种查看版本命令

安装opencv并查看其版本&#xff0c;直接通过一个可执行文件实现。 #!/bin/bashwget https://codeload.github.com/opencv/opencv/zip/3.4 -O opencv-3.4.zip && unzip opencv-3.4.zip && cd opencv-3.4 && \mkdir build && cd build &&a…
阅读更多...
Python | Leetcode Python题解之第142题环形链表II

Python | Leetcode Python题解之第142题环形链表II

题目&#xff1a; 题解&#xff1a; # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next Noneclass Solution(object):def detectCycle(self, head):""":type head: ListNode:…
阅读更多...
【C++题解】1389 - 数据分析

【C++题解】1389 - 数据分析

问题&#xff1a;1389 - 数据分析 类型&#xff1a;简单循环 题目描述&#xff1a; 该方法的操作方式为&#xff0c;如果要传递 2 个数字信息给友军&#xff0c;会直接传递给友军一个整数 n&#xff08;n 是一个 10 位以内的整数&#xff09;&#xff0c;该整数的长度代表要传…
阅读更多...
Linux安装MySQL教程【带图文命令巨详细】

Linux安装MySQL教程【带图文命令巨详细】

巨详细Linux安装MySQL 1、查看是否有自带数据库或残留数据库信息1.1检查残留mysql1.2检查并删除残留mysql依赖1.3检查是否自带mariadb库 2、下载所需MySQL版本&#xff0c;上传至系统指定位置2.1创建目录2.2下载MySQL压缩包 3、安装MySQL3.1创建目录3.2解压mysql压缩包3.3安装解…
阅读更多...
在线渲染3d怎么用？3d快速渲染步骤设置

在线渲染3d怎么用？3d快速渲染步骤设置

在线渲染3D模型是一种高效的技术&#xff0c;它允许艺术家和设计师通过互联网访问远程服务器的强大计算能力&#xff0c;从而加速渲染过程。无论是复杂的场景还是高质量的视觉效果&#xff0c;在线渲染服务都能帮助您节省宝贵的时间。 在线渲染3D一般选择的是&#xff1a;云渲染…
阅读更多...
Centos修改默认端口22

Centos修改默认端口22

修改Centos服务器ssh链接的默认端口22到任意端口&#xff0c;主要两个步骤&#xff1a; 修改配置文件&#xff0c;添加端口开放防火墙 一、 vim /etc/ssh/sshd_config 在文件中 #Port 22 行下增加 # Port 22 Port [修改后端口]注意&#xff1a; 这里 先将其中的#Port 22前的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023