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

代码随想录算法训练营第五十九天 |647. 回文子串、516.最长回文子序列、动态规划总结篇

一、647. 回文子串 

题目链接/文章讲解:代码随想录

 思考:

1.确定dp数组(dp table)以及下标的含义

如果本题定义dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话:

会发现很难找到递归关系,dp[i] 和 dp[i-1] ,dp[i + 1] 看上去都没啥关系,因此本题要从回文字符串的性质着手。

可以找到一种递归关系:

也就是判断一个子字符串(字符串的下表范围[i,j])是否回文,依赖于,子字符串(下表范围[i + 1, j - 1])) 是否是回文,为了明确这种递归关系,dp数组要定义成一位二维dp数组

bool dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。

2.确定递推公式

整体上是两种情况,就是s[i]与s[j]相等、不相等:

当s[i] = s[j],dp[i][j] = false。

当s[i] != s[j],有如下三种情况

  • 情况一:下标i 与 j相同,是同一个字符例如a,是回文子串
  • 情况二:下标i 与 j相差为1,例如aa,也是回文子串
  • 情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,要看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}
}

3.dp数组的初始化

dp[i][j]初始化为false

4.确定遍历顺序

从递推公式中可以看出,情况三是根据dp[i + 1][j - 1]是否为true,在对dp[i][j]进行赋值true的。dp[i + 1][j - 1] 在 dp[i][j]的左下角,如图:

从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的。

for (int i = s.size() - 1; i >= 0; i--) {  for (int j = i; j < s.size(); j++) {

5.举例推导dp数组

代码实现: 

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}}}}return result;}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n^2)

二、516.最长回文子序列

题目链接/文章讲解:代码随想录

思考:本题和回文子串思路其实差不多,但比求回文子串简单一点,因为情况少了一点

1.确定dp数组(dp table)以及下标的含义

dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

2.确定递推公式

如果s[i]与s[j]相同,dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同,dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

不相同说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

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]);
}

3.dp数组的初始化

从递推公式:dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况,所以需要手动初始化一下,当i与j相同,那么dp[i][j]等于1,其他情况dp[i][j]初始为0

vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

4.确定遍历顺序

dp[i][j] 依赖于 dp[i + 1][j - 1] ,dp[i + 1][j] 和 dp[i][j - 1]

所以遍历i的时候一定要从下到上遍历,j可以正常从左向右遍历。

for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); 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]);}}
}

5.举例推导dp数组

代码实现: 

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));for (int i = 0; i < s.size(); i++) dp[i][i] = 1;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i + 1; j < s.size(); 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][s.size() - 1];}
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n^2)

三、动态规划总结篇

题目链接/文章讲解:代码随想录

相关文章:

代码随想录算法训练营第五十九天 |647. 回文子串、516.最长回文子序列、动态规划总结篇

一、647. 回文子串 题目链接/文章讲解&#xff1a;代码随想录 思考&#xff1a; 1.确定dp数组&#xff08;dp table&#xff09;以及下标的含义 如果本题定义dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话&#xff1a; 会发现很难找到递归关系&#xff0c;dp[i] 和 dp[i-1]…...

互联网性能和可用性优化CDN和DNS

当涉及到互联网性能和可用性优化时&#xff0c;DNS&#xff08;Domain Name System&#xff09;和CDN&#xff08;Content Delivery Network&#xff09;是两个至关重要的元素。它们各自发挥着关键作用&#xff0c;以确保用户能够快速、可靠地访问网站和应用程序。在本文中&…...

使用 ErrorStack 在出现报错 ORA-14402 时产生的日志量

0、测试结论&#xff1a; 测试结果&#xff1a;设置 ErrorStack 级别为 1 时产生 Trace 的日志量最小&#xff0c;大小为 308K&#xff0c;同时在 alert 日志中也存在记录。 1、准备测试数据&#xff1a; sqlplus / as sysdba show pdbs alter session set containerpdb; …...

详解Spring-ApplicationContext

加载器目前有两种选择&#xff1a;ContextLoaderListener和ContextLoaderServlet。 这两者在功能上完全等同&#xff0c;只是一个是基于Servlet2.3版本中新引入的Listener接口实现&#xff0c;而另一个基于Servlet接口实现。开发中可根据目标Web容器的实际情况进行选择。 配…...

关键字extern、static与const

关键字extern、static与const extern关键字与include的区别 extern:于声明某个函数或变量是外部的(其他源文件中)include:用于批量引入 项目中可以根据需要引入的函数或变量数量决定使用extern还是include static关键字 static关键字用于限制函数和全局变量的作用域仅在当…...

虹科方案|国庆出游季,古建筑振动监测让历史古迹不再受损

全文导读&#xff1a; 国庆长假即将到来&#xff0c;各位小伙伴是不是都做好了出游计划呢&#xff1f;今年中秋、国庆“双节”连休八天&#xff0c;多地预计游客接待量将创下新高&#xff0c;而各地的名胜古迹更是人流爆满。迎接游客的同时&#xff0c;如何保障历史古迹不因巨大…...

Python学习笔记-使用哈希算法Hash,Hashlib进行数据加密

文章目录 一、概述1.1 哈希算法1.2 常见算法分类1.2.1 SHA算法1.2.2 MD4算法1.2.3 MD5算法 1.3 Hash算法的特性1.4 Hash算法的应用场景1.4.1 数据校验1.4.2 安全加密1.4.3 数字签名 二、Hash算法使用2.1 使用hash函数直接获取hash值2.2 使用hashlib库进行hash计算2.2.1 基本使用…...

跨境电商能否成为黄河流域产业带的新引擎?

近年来&#xff0c;随着全球贸易格局的不断演变和中国经济的快速崛起&#xff0c;跨境电商已经成为中国外贸的一大亮点。而在中国国内&#xff0c;黄河流域产业带一直以其丰富的资源和悠久的历史而闻名&#xff0c;但也面临着转型升级的挑战。那么&#xff0c;跨境电商是否有潜…...

从数据到决策:企业投资信息查询API的关键作用

前言 在现代商业环境中&#xff0c;数据是一项无价的资产。企业不仅需要访问大量数据&#xff0c;还需要将这些数据转化为有用的见解&#xff0c;以支持战略决策。对于企业投资而言&#xff0c;准确的信息和实时的市场数据至关重要。在这个信息时代&#xff0c;企业投资信息查…...

NSIC2050JBT3G 车规级120V 50mA ±15% 用于LED照明的线性恒流调节器(CCR) 增强汽车安全

随着汽车行业的巨大变革&#xff0c;高品质的汽车氛围灯效、仪表盘等LED指示灯效已成为汽车内饰设计中不可或缺的元素。深力科安森美LED驱动芯片系列赋能智能座舱灯效充满艺术感和科技感——NSIC2050JBT3G LED驱动芯片&#xff0c;实现对每路LED亮度和颜色进行细腻控制&#xf…...

LuatOS-SOC接口文档(air780E)-- ftp - ftp 客户端

ftp.login(adapter,ip_addr,port,username,password)# FTP客户端 参数 传入值类型 解释 int 适配器序号, 只能是socket.ETH0, socket.STA, socket.AP,如果不填,会选择平台自带的方式,然后是最后一个注册的适配器 string ip_addr 地址 string port 端口,默认21 string…...

第二证券:市净率高好还是低好?

市净率是一个衡量公司股票投资价值的指标&#xff0c;通过比较公司股票价格和公司每股净资产的比值来评估公司股票的估值水平。市净率高好还是低好这个问题并没有一个简单的答案&#xff0c;取决于具体的市场环境和投资者的需求。本文将从多个角度分析市净率高好还是低好。 首…...

HTTP协议是什么

HTTP (全称为 “超文本传输协议”) 是一种应用非常广泛的 应用层协议&#xff0c;是一种网络通信协议。 超文本&#xff1a;所谓 “超文本” 的含义, 就是传输的内容不仅仅是文本(比如 html, css 这个就是文本), 还可以是一些其他的资源, 比如图片, 视频, 音频等二进制的数据。…...

微服务09-Sentinel的入门

文章目录 微服务中的雪崩现象解决办法&#xff1a;1. 超时处理2. 舱壁模式3. 熔断降级4.流量控制 Sentinel1.介绍2.使用操作3.限流规则4.实战&#xff1a;流量监控5.高级选项功能的使用1.关联模式2.链路模式3.总结 流控效果1.预热模式2.排队等待模式3.总结4.热点参数限流5.实战…...

2023-2024-1 高级语言程序设计实验一: 选择结构

7-1 古时年龄称谓知多少&#xff1f; 输入一个人的年龄&#xff08;岁&#xff09;&#xff0c;判断出他属于哪个年龄段 &#xff1f; 0-9 &#xff1a;垂髫之年&#xff1b; 10-19&#xff1a; 志学之年&#xff1b; 20-29 &#xff1a;弱冠之年&#xff1b; 30-39 &#…...

js事件循环详解

事件循环简介 JavaScript的事件循环是一种处理异步事件和回调函数的机制&#xff0c;它是在浏览器或Node.js环境中运行&#xff0c;用于管理任务队列和调用栈&#xff0c;以及在适当的时候执行回调函数。 事件循环的基本原理是&#xff0c;JavaScript引擎在空闲时等待事件的到…...

实战指南:使用 kube-prometheus-stack 监控 K3s 集群

作者简介 王海龙&#xff0c;Rancher 中国社区技术经理&#xff0c;Linux Foundation APAC Evangelist&#xff0c;负责 Rancher 中国技术社区的维护和运营。拥有 9 年的云计算领域经验&#xff0c;经历了 OpenStack 到 Kubernetes 的技术变革&#xff0c;无论底层操作系统 Lin…...

golang调用scws实现简易中文分词

1、安装 scws 官网以及文档 https://github.com/hightman/scws wget -q -O - http://www.xunsearch.com/scws/down/scws-1.2.3.tar.bz2 | tar xjf -cd scws-1.2.3 ./configure --prefix/usr/local/scws --enable-shared make && make installLibraries have been ins…...

Excel 中使用数据透视图进行数据可视化

使用数据透视表&#xff08;PivotTable&#xff09;是在Excel中进行数据可视化的强大工具。下面将提供详细的步骤来使用数据透视表进行数据可视化。 **步骤一&#xff1a;准备数据** 首先&#xff0c;确保你有一个包含所需数据的Excel表格。数据应该按照一定的结构和格式组织…...

在SIP 语音呼叫中出现单通时要怎么解决?

在VoIP的环境中&#xff0c;特别是基于SIP通信的环境中&#xff0c;我们经常会遇到一些非常常见的问题&#xff0c;例如&#xff0c;单通&#xff0c;注册问题&#xff0c;回声&#xff0c;单通等。这些问题事实上都有非常直接的排查方式和解决办法&#xff0c;用户可以按照一定…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架

1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...

基于小程序老人监护管理系统源码数据库文档

摘 要 近年来&#xff0c;随着我国人口老龄化问题日益严重&#xff0c;独居和居住养老机构的的老年人数量越来越多。而随着老年人数量的逐步增长&#xff0c;随之而来的是日益突出的老年人问题&#xff0c;尤其是老年人的健康问题&#xff0c;尤其是老年人产生健康问题后&…...

el-amap-bezier-curve运用及线弧度设置

文章目录 简介示例线弧度属性主要弧度相关属性其他相关样式属性完整示例链接简介 ‌el-amap-bezier-curve 是 Vue-Amap 组件库中的一个组件,用于在 高德地图 上绘制贝塞尔曲线。‌ 基本用法属性path定义曲线的路径,可以是多个弧线段的组合。stroke-weight线条的宽度。stroke…...

PCA笔记

✅ 问题本质&#xff1a;为什么让矩阵 TT 的行列式为 1&#xff1f; 这个问题通常出现在我们对数据做**线性变换&#xff08;旋转/缩放&#xff09;**的时候&#xff0c;比如在 PCA 中把数据从原始坐标系变换到主成分方向时。 &#x1f4cc; 回顾一下背景 在 PCA 中&#xff…...

Go 并发编程基础:select 多路复用

select 是 Go 并发编程中非常强大的语法结构&#xff0c;它允许程序同时等待多个通道操作的完成&#xff0c;从而实现多路复用机制&#xff0c;是协程调度、超时控制、通道竞争等场景的核心工具。 一、什么是 select select 类似于 switch 语句&#xff0c;但它用于监听多个通…...

stm32—ADC和DAC

ADC和DAC 在嵌入式系统中&#xff0c;微控制器经常需要与现实世界的模拟信号进行交互。STM32微控制器内置了模拟数字转换器&#xff08;ADC&#xff09;和数字模拟转换器&#xff08;DAC&#xff09;&#xff0c;它们是实现这种交互的关键模块。 1. 模拟数字转换器&#xff08…...