动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数
一,最长回文串
1.题目
给你一个字符串
s,找出其中最长的回文子序列,并返回该序列的长度。子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
示例 1:
输入:s = "bbbab" 输出:4 解释:一个可能的最长回文子序列为 "bbbb" 。示例 2:
输入:s = "cbbd" 输出:2 解释:一个可能的最长回文子序列为 "bb" 。提示:
1 <= s.length <= 1000s仅由小写英文字母组成
2.题目接口
class Solution {
public:int longestPalindromeSubseq(string s) {}
};
3.解题思路及其代码
在思考这道题时,我们先想到的可能是dp[i]来作状态转移方程,表示以第i个位置为结尾的最长回文子序列。但是,我们是不能这样定义的。因为第i个位置能不能加入到这个子序列中是要看当前子序列的开头位置的字符是否与之匹配的。
在弄明白抛弃掉这种想法以后,我们便可以试着以区间dp的方式来解决:
1.状态表示:dp[i][j],表示在区间[i,j]的最长子序列。
2.状态转移方程:对于状态转移方程的推导需要分类讨论,分类如下:
在第二种情况下dp[i][j]要等于在这三种情况下的最大值,又因为dp[i+1][j-1]其实是在剩下的两种情况中包含的,所以dp[i][j] = max(dp[i+1][j],dp[i][j-1])。
代码:
根据以上思路写出代码如下:
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] = dp[i+1][j]的情况,所以要从下到上初始化{for(int j = i;j<n;j++)//j>=i{if(s[i] == s[j])//第一种情况{if(j>i) dp[i][j] = dp[i+1][j-1]+2;//j>i才能加2else dp[i][j] = 1;//i == j,个数为1}else//第二种情况{dp[i][j] = max(dp[i+1][j],dp[i][j-1]);//不用担心越界的情况,因为当j == 0时//i一定等于0,所以会在第一种情况中处理}}}return dp[0][n-1];}};
二,让字符串成为回文串的最小插入次数
1,题目
1312. 让字符串成为回文串的最少插入次数
提示
困难
218
相关企业
给你一个字符串
s,每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让
s成为回文串的 最少操作次数 。「回文串」是正读和反读都相同的字符串。
示例 1:
输入:s = "zzazz" 输出:0 解释:字符串 "zzazz" 已经是回文串了,所以不需要做任何插入操作。示例 2:
输入:s = "mbadm" 输出:2 解释:字符串可变为 "mbdadbm" 或者 "mdbabdm" 。示例 3:
输入:s = "leetcode" 输出:5 解释:插入 5 个字符后字符串变为 "leetcodocteel" 。提示:
1 <= s.length <= 500s中所有字符都是小写字母。
2.题目接口
class Solution {
public:int minInsertions(string s) {}
};
3.解题思路及其代码
对于这种回文串问题,因为有了上面的定义状态表示的经验所以还是使用一个二维的dp表解决问题。
1.状态表示:dp[i][j]表示在[i,j]这个区间内使这个区间内的字符串成为回文串的最小插入次数。
2.状态转移方程:在这里状态转移方程还是要分类讨论,还是要看s[i],s[j]是否相等:
在第二种情况下要取两者的较小值。
代码:
由以上思路写出代码如下:
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--)//有dp[i][j] = dp[i+1][j]+1的情况,所以要从下到上遍历{for(int j = i;j<n;j++){if(s[i] == s[j]){if(j>i) 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];} };
相关文章:
动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数
一,最长回文串 1.题目 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入&…...
CSS新手入门笔记整理:CSS列表样式
列表项符号:list-style-type 在HTML中,对于有序列表和无序列表的列表项符号,都是使用type属性来定义的。 语法 list-style-type:取值; list-style-type属性是针对ol或者ul元素的,而不是li元素。 有序列表属性 属性值 说明 …...
12月07日,每日信息差
以下是2023年12月07日的11条信息差 第一、社交媒体公司X计划在日本成立应用开发团队 第二、造车进程加快,小米汽车在多地招聘零售门店主管,零售门店主管工作地点涉及武汉、重庆、长沙、郑州、佛山、东莞、厦门等城市 第三、我国西南地区首座百万千瓦级…...
spring mvc理解
spring mvc M:model 模型 V:view 视图 C:controller 控制器 S: service 服务处理 D: Dao 数据持久化 视图 我理解就是web页面,帮助用户调用后端接口。 前后端分离之后,view似乎就和后端没什么关系了。 模型 格式…...
HTML-标签之文字排版、图片、链接、音视频
1、标签语法 HTML超文本标记语言——HyperText Markup Language 超文本是链接标记也叫标签,带尖括号的文本 2、HTML基本骨架 HTML基本骨架是网页模板 html:整个网页head:网页头部,存放给浏览器看的代码,例如CSSbody…...
圣诞将至—C语言圣诞树代码来啦
文章目录 圣诞将至—C实现语言圣诞树源码 圣诞将至—C实现语言圣诞树 圣诞树 源码 #define _CRT_SECURE_NO_WARNINGS#include <stdio.h> #include <math.h> #include <stdlib.h> #include <windows.h> #include <time.h> #define PI 3.14159265…...
Git常用命令#merge分支合并
要查看所有分支,包括本地和远程仓库的分支,可以使用以下命令: 1.查看分支 1.1 查看本地分支 git branch这个命令会列出本地所有的分支,当前所在的分支会有 * 标记。 1.2 查看远程分支 git branch -r这个命令会列出远程仓库的分…...
Windows server 2019 域环境部署
环境准备 准备3台服务器,配置都是8g2核,50g硬盘,操作系统版本Windows Server 2019 Datacenter 域服务器:adc,192.168.56.120服务器1:server1:,192.168.56.121服务器2:server2&…...
Cocos Creator加入图片没有被识别
原因,需要更换类型,选择下图中的类型...
java double类型保留两位小数并去除后面多余的0
public static void main(String[] args) {double value9.100001;//保留两位小数String format String.format("%.2f", value);//去除多余的0String strValue new BigDecimal(format).stripTrailingZeros().toPlainString();System.out.println("strValue &q…...
C++学习寄录(九.多态)
1.多态基本概念 先来看这样的代码,我的本意是想要输出“小猫在说话”,但实际输出的却是“动物在说话”。这是因为地址早绑定,在代码编译阶段就已经确定了函数地址;如果想要实现既定目标,那么这个dospeak(&…...
【Linux基础开发工具】yum生态vim的配置与使用
目录 前言 1. Linux 软件包管理器 yum 1.1 什么是yum 1.2 快速上手yum 1.3 yum生态 2. Linux编辑器vim 2.1 vim的模式 2.2 vim使用技巧 3. vim编辑器辅助功能配置 3.1 配置 3.2 用户sudo权限配置 总结 前言 Linux基础指令与权限之后,Linux系统开发工具的使用…...
java-HashMap、TreeMap、LinkedHashMap、ArrayList、LinkedList使用笔记
背景 Map<String, Integer> unsortedMap new HashMap<>(); unsortedMap.put("One", 1); unsortedMap.put("Two", 2); unsortedMap.put("Three", 3); unsortedMap.put("Four", 4); 一、关于排序 TreeMap&#…...
Oracle中mybatis批量更新报错ORA-00933:SQL命令未正确结束
项目场景: 最近在开发项目的过程中遇见了这个问题:Oracle中批量更新的时候报错 ORA-00933:SQL命令未正确结束 问题描述 mybatis批量更新报错ORA-00933:SQL命令未正确结束 <foreach item"item" index"index&q…...
Mysql综合案例练习<1>
MySql综合案例练习<1> 题目一题目二题目三题目四题目五题目六题目七题目八题目九题目十题目十一题目十二题目十三题目十四题目十五题目十六题目十七题目十八题目十九 题目一 创建数据库test01_library 创建表 books,表结构如下: CREATE DATABASE …...
Linux系统编程:线程总结
线程的概念 基本概念 所谓线程,通俗的说就是一个正在运行的函数。 在Linux系统中,线程是程序运行的最小单位,也被视为进程内部的控制序列。同一进程下的多个线程共享进程的所有资源,包括进程环境变量、打开的文件描述符、信号量…...
activemq启动成功但web管理页面却无法访问
前提: 在linux启动activemq成功!本地能ping通linux 处理方案: 确定防火墙是否关闭, 有两种处理方案:第一种-关闭防火墙;第二种-暴漏8161和61616两个端口 netstat -lnpt查看8161和61616端口 注意…...
【Flink on k8s】- 0 - Flink kubernetes operator 快速入门与实战
完整的课程,请点击链接。 目录 一、你将收获 二、适用人群 三、课程介绍...
毕设:《基于hive的音乐数据分析系统的设计与实现》
文章目录 环境启动一、爬取数据1.1、歌单信息1.2、每首歌前20条评论1.3、排行榜 二、搭建环境1.1、搭建JAVA1.2、配置hadoop1.3、配置Hadoop环境:YARN1.4、MYSQL1.5、HIVE(数据仓库)1.6、Sqoop(关系数据库数据迁移) 三、hadoop配置内存四、导…...
PHP使用HTTP代码示例模板
PHP是一种广泛用于服务器端的编程语言,它提供了许多内置的函数和扩展,以便开发人员能够轻松地处理HTTP请求和响应。在PHP中,您可以使用以下代码示例模板来处理HTTP请求和生成HTTP响应。 php复制代码 <?php // 处理GET请求 if ($…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
PydanticAI快速入门示例
参考链接:https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...
Java设计模式:责任链模式
一、什么是责任链模式? 责任链模式(Chain of Responsibility Pattern) 是一种 行为型设计模式,它通过将请求沿着一条处理链传递,直到某个对象处理它为止。这种模式的核心思想是 解耦请求的发送者和接收者,…...


