【面试算法——动态规划 19】最长回文子序列 (hard)让字符串成为回文串的最少插入次数

516. 最长回文子序列

链接: 516. 最长回文子序列

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = “bbbab”
输出:4
解释:一个可能的最长回文子序列为 “bbbb” 。
示例 2:

输入:s = “cbbd”
输出:2
解释:一个可能的最长回文子序列为 “bb” 。

1.状态表示*
. 状态表⽰:
关于「单个字符串」问题中的「回⽂⼦序列」,或者「回⽂⼦串」,我们的状态表⽰研究的对象⼀般都是选取原字符串中的⼀段区域 [i, j] 内部的情况。这⾥我们继续选取字符串中的⼀段区域来研究:
dp[i][j] 表⽰:s字符串 [i, j] 区间内的所有的⼦序列中,最⻓的回⽂⼦序列的⻓度

2.状态转移方程
i. 当⾸尾两个元素「相同」的时候,也就是 s[i] == s[j] :那么 [i, j] 区间上的最
⻓回⽂⼦序列,应该是 [i + 1, j - 1] 区间内的那个最⻓回⽂⼦序列⾸尾填上
s[i] 和 s[j] ,此 dp[i][j] = dp[i + 1][j - 1] + 2

ii. 当⾸尾两个元素不「相同」的时候,也就是 s[i] != s[j] :此时这两个元素就不能同时添加在⼀个回⽂串的左右,那么我们就应该让 s[i] 单独加在⼀个序列的左边,或者让 s[j] 单独放在⼀个序列的右边,看看这两种情况下的最⼤值:
• 单独加⼊ s[i] 后的区间在 [i, j - 1] ,此时最⻓的回⽂序列的⻓度就是
dp[i][j - 1] ;
• 单独加⼊ s[j] 后的区间在 [i + 1, j] ,此时最⻓的回⽂序列的⻓度就是
dp[i+ 1][j] ;
取两者的最⼤值,于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])

3. 初始化
我们的初始化⼀般就是为了处理在状态转移的过程中,遇到的⼀些边界情况,因为我们需要根据状
态转移⽅程来分析哪些位置需要初始化。
根据状态转移⽅程 dp[i][j] = dp[i + 1][j - 1] + 2 ,我们状态表⽰的时候,选取的
是⼀段区间,因此需要要求左端点的值要⼩于等于右端点的值,因此会有两种边界情况:
i. 当 i == j 的时候, i + 1 就会⼤于 j - 1 ,此时区间内只有⼀个字符。这个⽐较好分析, dp[i][j] 表⽰⼀个字符的最⻓回⽂序列,⼀个字符能够⾃⼰组成回⽂串,因此此时 dp[i][j] = 1 ;

ii. 当 i + 1 == j 的时候, i + 1 也会⼤于 j - 1 ,此时区间内有两个字符。这样也
好分析,当这两个字符相同的时候, dp[i][j] = 2 ;不相同的时候, d[i][j] =0 。
对于第⼀种边界情况,我们在填表的时候,就可以同步处理。
对于第⼆种边界情况, dp[i + 1][j - 1] 的值为 0 ,不会影响最终的结果,因此可以不⽤考虑。

4. 填表顺序
因此我们的填表顺序应该是「从下往上填写每⼀⾏」,「每⼀⾏从左往右」

5. 返回值
需要返回dp[0][n - 1]

代码:

 int longestPalindromeSubseq(string s) {int n=s.size();//表示 i~j中最长子序列的长度vector<vector<int>> dp(n,vector<int>(n));for(int i=n-1;i>=0;i--){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;}else{dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][n-1];}

在这里插入图片描述

1312. 让字符串成为回文串的最少插入次数

链接: 1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1:

输入:s = “zzazz”
输出:0
解释:字符串 “zzazz” 已经是回文串了,所以不需要做任何插入操作。
示例 2:

输入:s = “mbadm”
输出:2
解释:字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
示例 3:

输入:s = “leetcode”
输出:5
解释:插入 5 个字符后字符串变为 “leetcodocteel” 。

1.状态表示*
. 状态表⽰:
关于「单个字符串」问题中的「回⽂⼦序列」,或者「回⽂⼦串」,我们的状态表⽰研究的对象⼀般都是选取原字符串中的⼀段区域 [i, j] 内部的情况。这⾥我们继续选取字符串中的⼀段区域来研究:
dp[i][j] 表⽰:s字符串 [i, j] 区间内的所有的⼦序列中,成为回⽂⼦串的最少插⼊次数

2.状态转移方程
关于「回⽂⼦序列」和「回⽂⼦串」的分析⽅式,⼀般都是⽐较固定的,都是选择这段区域的「左右端点」的字符情况来分析。因为如果⼀个序列是回⽂串的话,「去掉⾸尾两个元素之后依旧是回⽂串」,「⾸尾加上两个相同的元素之后也依旧是回⽂串」。因为,根据「⾸尾元素」的不同,可以分为下⾯两种情况:

i. 当⾸尾两个元素「相同」的时候,也就是 s[i] == s[j] :

  1. 那么 [i, j] 区间内成为回⽂⼦串的最少插⼊次数,取决于 [i + 1, j - 1] 区间
    内成为回⽂⼦串的最少插⼊次数;
  2. 若 i == j 或 i == j - 1 ( [i + 1, j - 1] 不构成合法区间),此时只有1~2个相同的字符, [i, j] 区间⼀定是回⽂⼦串,成为回⽂⼦串的最少插⼊次数是0。
    此时 dp[i][j] = i >= j - 1 ? 0 : dp[i + 1][j - 1] ;

ii. 当⾸尾两个元素「不相同」的时候,也就是 s[i] != s[j] :

  1. 此时可以在区间最右边补上⼀个 s[i] ,需要的最少插⼊次数是 [i + 1, j] 成为回
    ⽂⼦串的最少插⼊次数+本次插⼊,即 dp[i][j] = dp[i + 1][j] + 1 ;
  2. 此时可以在区间最左边补上⼀个 s[j] ,需要的最少插⼊次数是 [i, j + 1] 成为回
    ⽂⼦串的最少插⼊次数+本次插⼊,即 dp[i][j] = dp[i][j + 1] + 1 ;
    综上所述,状态转移⽅程为:

▪ 当 s[i] == s[j] 时: dp[i][j] = i >= j - 1 ? 1 : dp[i + 1][j -1] 。
▪ 当 s[i] != s[j] 时: dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) +1 。

3. 初始化
无需初始化

4. 填表顺序
因此我们的填表顺序应该是「从下往上填写每⼀⾏」,「每⼀⾏从左往右」

5. 返回值
需要返回dp[0][n - 1]

代码:

 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+1][j],dp[i][j-1])+1;}}}return dp[0][n-1];}

在这里插入图片描述

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

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

相关文章

opencv for unity package在unity中打开相机不需要dll

下载OpenCV for Unity 导入后&#xff0c;里面有很多案例 直接打开就可以运行 打开相机

TCP 和 UDP哪个更好

传输控制协议 &#xff08;TCP&#xff09; 和用户数据报协议 &#xff08;UDP&#xff09; 是互联网的基础支柱&#xff0c;支持从网络源到目的地的不同类型的数据传输。TCP更可靠&#xff0c;而UDP优先考虑速度和效率。本文解释了两种协议的工作原理&#xff0c;并详细讨论了…

vuejs - - - - - 使用code编辑器codemirror

使用code编辑器codemirror 0. 效果图1. 依赖安装2. 组件封装3. 组件使用 0. 效果图 列表实现参考: 列表实现代码 1. 依赖安装 npm install codemirror codemirror-editor-vue3 jsonlint-mod 2. 组件封装 code-mirror-editor.vue <template><VueCodeMirrorclas…

Java之IO流概述

1.1 什么是IO 生活中&#xff0c;你肯定经历过这样的场景。当你编辑一个文本文件&#xff0c;忘记了ctrls &#xff0c;可能文件就白白编辑了。当你电脑上插入一个U盘&#xff0c;可以把一个视频&#xff0c;拷贝到你的电脑硬盘里。那么数据都是在哪些设备上的呢&#xff1f;键…

Nginx WEB访问与Linux授权约束

看到所有文件的权限都是没有的&#xff0c;即便所有的权限都没有即使nginx做了配置&#xff0c;这些都是正确的。那么在浏览器真正去访问的时候是不能访问的。 [rootjenkins html]# ls -l total 4 drwxr-xr-x 2 root root 23 Sep 16 17:43 dist ---------- 1 root root 33 Sep …

利用C++开发一个迷你的英文单词录入和测试小程序-增强功能

小玩具基本完成之后&#xff0c;在日常工作中&#xff0c;记录一些单词&#xff0c;然后定时再复习下&#xff0c;还真的有那么一点点用&#xff08;毕竟自己做的小玩具&#xff09;。 在使用过程中&#xff0c;遇到不认识的单词&#xff0c;总去翻译软件翻译&#xff0c;然后…

蓝桥杯每日一题2023.9.24

九进制转十进制 - 蓝桥云课 (lanqiao.cn) 题目描述 分析 #include<bits/stdc.h> using namespace std; int main() {cout << 2 * 9 * 9 * 9 0 * 9 * 9 2 * 9 2;return 0; } 顺子日期 - 蓝桥云课 (lanqiao.cn) 题目描述 分析 全部枚举 #include<bits/s…

MAC word 如何并列排列两张图片

系统&#xff1a;MAC os 参考博客 https://baijiahao.baidu.com/s?id1700824516945958911&wfrspider&forpc 步骤1 新建一个word文档和表格 修改表格属性 去掉自动重调尺寸以适应内容 插入图片 在表格的位置插入对应的图片如下 去除边框 最终结果如下

腾讯mini项目-【指标监控服务重构】2023-08-27

今日已办 Docker Monitoring with cAdvisor, Prometheus and Grafana Docker Monitoring with cAdvisor, Prometheus and Grafana | by Mertcan Simsek | MediumMonitoring Docker container metrics using cAdvisor | Prometheus prometheus.yml global:scrape_interval: …

macOS 下 Termius 中文显示为乱码

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…

94 # express 兼容老的路由写法

上一节实现了错误处理中间件&#xff0c;这一节来实现兼容老的路由写法 看个 express 的二级路由的例子 const express require("express"); const userRouter require("./routes/userRouter"); const articleRouter require("./routes/articleR…

Python爬虫技术系列-02HTML解析-xpath与lxml

Python爬虫技术系列-02HTML解析-xpath与lxml 2 XPath介绍与lxml库2.1 XPath概述2.2 lxml库介绍2.2.1 lxml库安装2.2.2 lxml库基本使用2.2.3 lxml案例a.读取数据并补全b.读取数据并选取节点&#xff1a; 2 XPath介绍与lxml库 参考连接&#xff1a; XPath教程 https://www.w3sch…

高效管理生活:Microsoft To Do for Mac 微软待办事项软件

在日常生活中&#xff0c;我们经常面临着琐碎的任务和繁忙的安排。为了更好地管理自己的时间和事务&#xff0c;一款强大而智能的待办事项软件是必不可少的。Microsoft To Do for Mac 微软待办事项软件将助您高效管理生活&#xff0c;让每件事都尽在掌握。 Microsoft To Do fo…

腾讯mini项目-【指标监控服务重构-会议记录】2023-07-26

2023-07-26组长会议纪要 A组 项目对齐和问题 分配需求&#xff0c;SLI指标上报&#xff0c;暂时没有实际效果 每个人负责一条指标&#xff0c;同步代码&#xff0c;时间问题还是难题跟B组同学请教&#xff0c;答疑 问题&#xff1a;启动 Tracer 【已解决】 环境问题&#xf…

数据结构:堆的简单介绍

目录 堆的介绍:(PriorityQueue) 大根堆:根节点比左右孩子节点大 小根堆:根节点比左右孩子节点小 堆的存储结构: 为什么二叉树在逻辑上用满二叉树结构,而不是普通二叉树呢? 因为如果是普通二叉树会造成资源的浪费​编辑 堆的介绍:(PriorityQueue) 堆又称优先级队列,何为优先…

uni-app使用HBuilder X编辑器本地打包apk步骤说明

1.下载安装Android Studio 下载地址官方地址&#xff1a;Android Studio 下载文件归档 | Android 开发者 | Android Developers 安装Android SDK和Google USB Driver即可&#xff0c;后者主要是为了后期使用USB设置的&#xff0c;如果不需要可以不点。 2.下载uni-app提供…

ElementUI之登陆+注册->饿了吗完成用户登录界面搭建,axios之get请求,axios之post请求,跨域,注册界面

饿了吗完成用户注册登录界面搭建axios之get请求axios之post请求跨域注册界面 1.饿了吗完成用户注册登录界面搭建 将端口号8080改为8081 导入依赖&#xff0c;在项目根目录使用命令npm install element-ui -S&#xff0c;添加Element-UI模块 -g&#xff1a;将依赖下载node_glod…

大数据flink篇之一-基础知识

一、起源 2010至2014年间&#xff0c;由柏林工业大学、柏林洪堡大学和哈索普拉特纳研究所联合发起名Stratosphere的研究项目。2014年4月&#xff0c;项目贡献给Apache基金会&#xff0c;成为孵化项目。更名为Flink2014年12月&#xff0c;成为基金会顶级项目2015年9月&#xff…

02 MIT线性代数-矩阵消元 Elimination with matrices

一, 消元法 Method of Elimination 消元法是计算机软件求解线形方程组所用的最常见的方法。任何情况下&#xff0c;只要是矩阵A可逆&#xff0c;均可以通过消元法求得Axb的解 eg: 我们将矩阵左上角的1称之为“主元一”&#xff08;the first pivot&#xff09;&#xff0c;第…

算法-贪心+优先级队列-IPO

算法-贪心优先级队列-IPO 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/ipo/description/?envTypestudy-plan-v2&envIdtop-interview-150 1.2 题目描述 2 回溯法 2.1 思路 2.2 代码 class Solution {int result 0;public int findMaximizedCapital(int …