当前位置: 首页 > news >正文

动态规划-回文串系列——1312.让字符串变成回文串的最小插入次数

1.题目解析

题目来源:1312.让字符串变成回文串的最小插入次数——力扣

测试用例

2.算法原理

1.状态表示

一维dp表无法存储任意区间内将字符串变为回文子串的最小插入次数,所以使用二维dp表存储将[i,j]区间的字符串变为回文子串的最小插入次数

dp[i][j]:将[i,j]区间的字符串变为回文子串的最小插入次数

2.状态转移方程

这里首先判断两端字符是否相同,如果相同则需要判断[i,j]区间字符个数,然后向中间移动取dp表的值,反之不相同则需要对左插与右插两种情况取min值

3.初始化

dp表只有中间对角线与中间对角线的右上方对角线两条路线可能会用到下三角的值,但是下三角全为0不影响填表,因此不用初始化

4.填表顺序

填写时可能用到左下角或者左边与正下方的值,所以填表需要从下至上且每行从左到右

5.返回值 

根据状态表示可以直接返回dp[0][n-1]

3.实战代码

代码解析

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

 


http://www.mrgr.cn/news/64201.html

相关文章:

  • 蓝桥杯-扫雷
  • 计算矩阵边缘元素之和
  • 前端用到的一些框架
  • 面试题-RocketMQ的基本架构、支持的消息模式、如何保证消息的可靠传输
  • Kafka的学习路径规划
  • AtomicIntegerFieldUpdater能否降低内存
  • 祖鲁法则精要
  • 实习冲刺Day11
  • 如何利用8款工具辅助建立需求管理体系
  • CAN协议
  • 【P2-1】ESP8266 WIFI模块STA、AP、STA+AP、TCP/UDP透传工作模式介绍与AT指令介绍
  • Aicbo:解锁AI创意新纪元,一键生成视频、绘画与文字!
  • gesp的python二级题目
  • python 调用shell 脚本
  • 【机器学习】机器学习算法-线性回归算法
  • springboot河南旅游推荐系统-计算机毕业设计源码33358
  • DNS域名解析服务器--RHCE
  • Git本地分支更新推送到远程主分支上
  • 1231243545347ikih
  • 江协科技STM32学习- P33 实验-软件I2C读写MPU6050
  • 裸金属服务器和普通服务器的不同之处
  • 决策树算法
  • Java实战项目-基于 SpringBoot+Vue 的医院管理系统
  • Qt的程序如何打包详细教学
  • 无桥图腾柱PFC -- 基于平均电流的双闭环仿真
  • 【多模态RAG】多模态RAG ColPali实践