2023-08-20力扣今日二题
链接:
1312. 让字符串成为回文串的最少插入次数
题意:
如题
解:
动态规划,枚举回文串中点并递增回文串长度
初始状态若L==R则单个字符为中点,需要添加0个字符成为回文串;若L+1==R则如果S[L]==S[R]则需要添加0个字符成为回文串,否则添加1个字符(选其一但是并不需要知道加的是那个)
状态转移:
如果S[L]!=S[R]则DP[L][R] == min(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i + 1][j - 1]+1),但是dp[i + 1][j - 1]+1其实至少等价于其中之一,比如abc需要添加a和c变成acbca或cabac,那么ab和bc都为1,abc+2==(ab+1)+1==(bc+1)+1;或者aac需要添加c,ac需要添加1,aa需要添加0,则aac+1==(aa)+1<=(ac+1)+1
如果s[L]==S[R],则DP[L][R]=min(DP[L][R],DP[L+1][R-1])
实际代码:
#include<bits/stdc++.h>
using namespace std;
int minInsertions(string s)
{int lg=s.size();vector<vector<int>> dp(lg,vector<int>(lg,0x3f3f3f3f));for(int i=0;i<lg;i++) dp[i][i]=0;for(int t=1;t<lg;t++)//递增推导长度 {for(int i=0;i+t<lg;i++)//递增起点 {if(t==1){if(s[i]==s[i+t]) dp[i][i+t]=0;else dp[i][i+t]=1;}else{dp[i][i+t]=min(dp[i][i+t-1]+1,dp[i+1][i+t]+1);if(s[i]==s[i+t]) dp[i][i+t]=min(dp[i][i+t],dp[i+1][i+t-1]);}}}return dp[0][lg-1];
}
int main()
{string s;cin>>s;int ans=minInsertions(s);cout<<ans<<endl;return 0;
}
限制:
1 <= s.length <= 500s中所有字符都是小写字母。
相关文章:
2023-08-20力扣今日二题
链接: 1312. 让字符串成为回文串的最少插入次数 题意: 如题 解: 动态规划,枚举回文串中点并递增回文串长度 初始状态若LR则单个字符为中点,需要添加0个字符成为回文串;若L1R则如果S[L]S[R]则需要添加…...
【地理专题】2023年最新全国A级景区数
数据来源:中国文化和旅游部时间跨度:2023年区域范围:全国范围数据字段: 景区名称;地址;等级;城市;经度;纬度 该图基于自然资源部地图技术审查中心标准地图服务网站下载…...
Elasticsearch实战(一):Springboot实现Elasticsearch统一检索功能
文章目录 系列文章索引一、准备工作1、搭建docker环境2、安装eskibana3、es安装ik分词器(1)下载安装(2)测试 4、Springboot(1)引包(2)客户端公共方法(3)公共实…...
更改计算机睡眠时间
控制面板–>系统和安全–>电源选项下的更改计算机睡眠时间 如果关闭显示器时间小于使计算机进入睡眠状态时间,时间先到达关闭显示器时间,显示器关闭,这时电脑还在正常工作状态。如果此时敲击键盘显示器出现画面,无需输入密…...
Matplotlib数据可视化(一)
目录 1.Matplotlib简介 2.Matplotlib绘图基础 2.1 创建画布与子图 2.2 添加画布属性 2.3 绘图的保存与显示 1.Matplotlib简介 Matplotlib是一个用于绘制数据可视化图表的Python库。它提供了广泛的功能和灵活性,可以创建各种类型的图表,包括折线图、…...
LLM提示词工程和提示词工程师Prompting and prompt engineering
你输入模型的文本被称为提示,生成文本的行为被称为推断,输出文本被称为完成。用于提示的文本或可用的内存的全部量被称为上下文窗口。尽管这里的示例显示模型表现良好,但你经常会遇到模型在第一次尝试时无法产生你想要的结果的情况。你可能需…...
Python开发环境(Visual Studio Code、Anaconda、PyInstaller、Enigma Virtual Box)
Python开发环境 [Anaconda、PyInstaller、Enigma Virtual Box] AnacondaAnaconda安装搭建Python环境Anaconda命令 Visual Studio CodeVisual Studio Code中Python设置Visual Studio Code中使用Qt Designer Python打包发布.exe可执行文件PyinstallerEnigma Virtual Box Anaconda…...
Unreal Engine 测试总结
Android 项目打包应选择哪种纹理格式?打包模式区别? 根据官网文档介绍,建议使用 ETC2:所有OpenGL 3.x 类型的设备都支持,并且支持alpha压缩 打包模式包括:内部测试阶段的开发模式,对外发布的发行…...
Air780EG —— 合宙4G定位解决方案
定位模式: 外部单片机控制模式(常见于AT固件客户): 开机 -> 搜星 -> 定位成功 -> 上报 -> 关机 780E自行控制模式(常见于二次开发客户,AT用户也可以使用): 开机 -> 搜星 -> 定位成功 -> 模块休眠,关闭GP…...
【算法刷题之数组篇(2)】
目录 1.leetcode-35. 搜索插入位置(简单)2.leetcode-74. 搜索二维矩阵(中等)3.leetcode-73. 矩阵置零(中等)4.leetcode-56. 合并区间(中等)5.leetcode-54. 螺旋矩阵(中等…...
chromedriver.exe 的所有版本下载地址
Chrome for Testing availability 上面的网址是V115 v116.... 以上的。 CNPM Binaries Mirror 上面这个是V115版本以下的。 这个文章没有任何实际价值,记录的原因是因为突然发现过去的py无法运行,原因是chrome浏览器偷偷升级到V115,于是找…...
C++ 网络编程项目fastDFS分布式文件系统(四)-fastCGI项目相关技术以及linux搜狗输入法相关问题。
目录 1. Nginx作为web服务器处理请求 2. http协议复习 Get方式提交数据 Post方式提交数据 3. fastCGI 3.1 CGI 3.2 fastCGI 3.3 fastCGI和spawn-fcgi安装 1. 安装fastCGI 2. 安装spawn-fcgi 3.4 nginx && fastcgi 4其他知识点 1. fastCGI环境变量 - fas…...
【HarmonyOS】服务卡片 API6 JSUI跳转不同页面
【引言】 “JS卡片支持为组件设置action,包括router事件和message事件,其中router事件用于应用跳。若设置router事件,则action属性值为"router";abilityName为卡片提供方应用的跳转目标Ability名;params中的…...
【linux】debian10安装vim
debian10.0上用apt vim安装vim提示依赖的版本冲突。后来发现是软件源没有添加更新源buster-updates。 以下是问答。 问:debian10怎么安装vim? 答: 在 Debian 10 系统上安装 Vim 的方法很简单,主要有以下两种: 1. 使用 apt 命令安装 bash sudo apt u…...
文件同步工具rsync
文章目录 作用特性安装命令服务端启动增加安全认证及免密登录 实时推送源服务器配置结合inotify实现实时推送 参数详解 学些过程中遇到的问题 作用 rsync是linux系统下的数据镜像备份工具。使用快速增量备份工具Remote Sync可以远程同步,支持本地复制,或…...
【嵌入式开发 Linux 常用命令系列 12 -- linux 下 log 输出重定向 详细介绍 】
文章目录 Linux 输出重定向使用背景Linux 重定向使用介绍 上篇文章:嵌入式开发 Linux 常用命令系列 11 – linux 下 任务与CPU绑定命令 taskset 详细介绍 Linux 输出重定向使用背景 在Linux中,输入和输出重定向是非常常见的操作,它们可以用…...
gin中关于参数注入问题
关于参数注入的问题 如果在开发中一旦发小参数没有按照既定的要求注入到结构体的话,这个时候就一定要看请求方式什么?如果是post请求、 前端—post—json{id:1,pageSize:10,page:1}———————————- 参数注入方法:ShouldBindJSON p…...
记录首次面试2023-08-18
人生第一次面试,大概一个小时左右。没有问我C的,上来一个数据库事务,虽然没有复习,但是还是能够记住一些,主要问的一些事务的隔离级别,以及都有什么作用,我是举例回答的,客户端A和客…...
【Apollo学习笔记】——规划模块TASK之LANE_CHANGE_DECIDER
文章目录 前言LANE_CHANGE_DECIDER功能简介LANE_CHANGE_DECIDER相关配置LANE_CHANGE_DECIDER总体流程LANE_CHANGE_DECIDER相关子函数PrioritizeChangeLaneUpdateStatusIsClearToChangeLaneHysteresisFilter 参考 前言 在Apollo星火计划学习笔记——Apollo路径规划算法原理与实…...
rabbitmq的死信队列
目录 成为死信的条件 消息TTL过期 队列达到最大长度 消息被拒 延迟队列 延迟队列使用场景 消息设置 TTL 队列设置 TTL 两者区别 producer 将消息投递到 broker 或者直接到 queue 里了, consumer 从 queue 取出消息 进行消费,但某些时候由…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
