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

代码随想录 (programmercarl.com)

647. 回文子串

1.dp数组及下标含义

我们在判断字符串S是否是回文,那么如果我们知道 s[1],s[2],s[3] 这个子串是回文的,那么只需要比较 s[0]和s[4]这两个元素是否相同,如果相同的话,这个字符串s 就是回文串。

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

2.递推公式

当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。

3.初始化

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

4.遍历顺序

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

class Solution {public int countSubstrings(String s) {int len = s.length();int res = 0;boolean[][] dp = new boolean[len][len];for (int i = len - 1; i >= 0; i--) {for (int j = i; j < len; j++) {if (s.charAt(i) != s.charAt(j)){dp[i][j] = false;}else {if (j - i <= 1){res++;dp[i][j] = true;}else {if (dp[i + 1][j - 1]){res++;dp[i][j] = true;}}}}}return res;}
}

注意:j的遍历开始于i

516.最长回文子序列

LC.617字串==必须连续;LC.516回文子序列===可不连续

1.dp数组及下标含义

dp[i][j]:表示[i, j]范围内的回文子序列长度

2.递推公式

1)当s[i]与s[j]相等时,dp[i][j] = dp[i + 1][j - 1] + 2

2)当s[i]与s[j]不相等时,

不要s[i],要s[j]的回文子序列长度为dp[i + 1][j];

不要s[j],要s[i]的回文子序列长度为dp[i][j - 1]。

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

3.初始化

初始化的是递推公式的根基,即i + 1 == j - 1的时候,需要初始化才能够进行递推。

dp[i][i] = 1; 表示同一个字符,其最长回文子序列大小为1

4.遍历顺序

从左往右,从下往上

class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len + 1][len + 1];for (int i = len - 1; i >= 0; i--) {dp[i][i] = 1;for (int j = i + 1; j < len; j++) {//j = i + 1是因为在i = 0的时候,如果j = i的话,j - 1就越界了if (s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i + 1][j - 1] + 2;}else{dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][len - 1];}
}

动态规划总结篇

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

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

相关文章

斯坦福和 Meta学者发现Gemini在常识推理任务中有较强潜力;初学者GPT:Ai和LLM资源

&#x1f989; AI新闻 &#x1f680; 斯坦福和 Meta学者发现Gemini在常识推理任务中有较强潜力 摘要&#xff1a;斯坦福和Meta的学者发表论文为Gemini正名&#xff0c;他们发现之前对Gemini的评估并不能完全捕捉到其真正的常识推理潜力。他们设计了需要跨模态整合常识知识的任…

鸿蒙开发第一天

一、开发准备工作 1、开发工具的安装 1&#xff09;下载地址&#xff1a;https://developer.huawei.com/consumer/cn/deveco-studio/ 2&#xff09;查询API文档链接&#xff1a;https://developer.huawei.com/consumer/cn/doc/harmonyos-references-V2/syscap-00000014080893…

m3u8网络视频文件下载方法

在windows下&#xff0c;使用命令行cmd的命令下载m3u8视频文件并保存为mp4文件。 1.下载ffmpeg&#xff0c;访问FFmpeg官方网站&#xff1a;https://www.ffmpeg.org/进行下载 ffmpeg下载&#xff0c;安装&#xff0c;操作说明 https://blog.csdn.net/m0_53157282/article/det…

PACC:数据中心网络的主动 CNP 生成方案

PACC&#xff1a;数据中心网络的主动 CNP 生成方案 文章目录 PACC&#xff1a;数据中心网络的主动 CNP 生成方案PACC算法CNP数据结构PACC参数仿真结果参考文献 PACC算法 CNP数据结构 PACC参数 仿真结果 PACC Hadoop Load0.2 的情况&#xff1a; PACC Hadoop Load0.4 的情况&a…

基于机器视觉的害虫种类及计数检测研究-人工智能项目-附代码

概述 农业与民生和经济发展息息相关&#xff0c;对农业发展科学化的关注既是民生需求&#xff0c; 也是经济稳步发展的迫切需求。病虫害是影响农作物生长的重要因素&#xff0c;对农作物的产量和品质都能造成无法估计的损害。 - 针对目前广大农业产区农业植保人员稀缺、病虫害…

Docker与虚拟机的比对

在Windows操作系统上的对比&#xff1a; 但是官方还是建议我们尽量不要将Docker直接安装到Windows操作系统上。

2024第一篇: 架构师成神之路总结,你值得拥有

大家好&#xff0c;我是冰河~~ 很多小伙伴问我进大厂到底需要怎样的技术能力&#xff0c;经过几天的思考和总结&#xff0c;终于梳理出一份相对比较完整的技能清单&#xff0c;小伙伴们可以对照清单提前准备相关的技能&#xff0c;在平时的工作中注意积累和总结。 只要在平时…

达梦数据库安装超详细教程(小白篇)

文章目录 达梦数据库一、达梦数据库简介二、达梦数据库下载三、达梦数据库安装1. 解压2. 安装 四、初始化数据库五、DM管理工具 达梦数据库 一、达梦数据库简介 ​ 达梦数据库管理系统是达梦公司推出的具有完全自主知识产权的高性能数据库管理系统&#xff0c;简称DM。 达梦数…

(湖科大教书匠)计算机网络微课堂(下)

第四章、网络层 网络层概述 网络层主要任务是实习网络互连&#xff0c;进而实现数据包在各网络之间的传输 因特网使用TCP/IP协议栈 由于TCP/IP协议栈的网络层使用网际协议IP&#xff0c;是整个协议栈的核心协议&#xff0c;因此TCP/IP协议栈的网络层常称为网际层 网络层提供…

Java 流程控制语句

程序设计中规定的三种流程结构&#xff0c;即&#xff1a; 顺序结构 程序从上到下逐行地执行&#xff0c;中间没有任何判断和跳转 分支结构 根据条件&#xff0c;选择性地执行某段代码 有 if…else 和 switch-case 两种分支语句 循环结构 根据循环条件&#xff0c;重复性的执…

Yapi安装配置(CentOs)

环境要求 nodejs&#xff08;7.6) mongodb&#xff08;2.6&#xff09; git 准备工作 清除yum命令缓存 sudo yum clean all卸载低版本nodejs yum remove nodejs npm -y安装nodejs,获取资源,安装高版本nodejs curl -sL https://rpm.nodesource.com/setup_8.x | bash - #安装 s…

交换机03_基本配置

一、思科设备的命令行基础 1、进入设备的命令行界面 设备支持命令行 去查看设备上的接口&#xff0c;是否有console口需要有console线 右击此电脑设备管理器需要通过超级终端软件进行连接&#xff0c;如putt、secret CRT、xshell等软件 &#xff08;1&#xff09;思科模拟器…

在 Linux 中使用 cat 命令

cat 命令用于打印文本文件的文件内容。至少&#xff0c;大多数 Linux 用户都是这么做的&#xff0c;而且没有什么问题。 cat 实际上代表 “连接(concatenate)”&#xff0c;创建它是为了 合并文本文件。但只要有一个参数&#xff0c;它就会打印文件内容。因此&#xff0c;它是用…

ASP.NETCore WebAPI 入门 杨中科

ASP.NETCore WebAPI入门1 回顾 mvc开发模式 前端代码和后端代码是混在一个项目之中 WEB API 1、什么是结构化的Http接口。Json。 2、Web API项目的搭建。 3、Web API项目没有Views文件夹。 4、运行项目&#xff0c;解读代码结构。 5、【启用OpenAPI支持】→>swagger,在界…

基于SSM的新闻网站

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

性能测试之(六):JMeter 元件

元件&#xff08;多个类似功能组件的容器&#xff09; 组件&#xff1a;封装的方法&#xff0c;比如取样器中的发送请求的方法 一、常见的元件 1、取样器&#xff1a;发送请求2、逻辑处理&#xff1a;控制语句执行顺序3、前置处理器&#xff1a;在请求&#xff08;取样器&…

Linux内核中断

Linux内核中断 ARM里当按下按键的时候&#xff0c;他首先会执行汇编文件start.s里面的异常向量表里面的irq,在irq里面进行一些操作。 再跳转到C的do_irq(); 进行操作&#xff1a;1&#xff09;判断中断的序号&#xff1b;2&#xff09;处理中断&#xff1b;3&#xff09;清除中…

根本记不住MySQL进阶查询语句

1 MySQL进阶查询 1.1 MySQL进阶查询的语句 全文以数据库location和Store_Info为实例 ---- SELECT ----显示表格中一个或数个字段的所有数据记录 语法&#xff1a;SELECT "字段" FROM "表名"; select 列名 from 表名 ; ---- DISTINCT ----不显示重复的数…

UntiyShader(五)属性、内置文件和变量

目录 一、如何使用属性 例子 ShaderLab中的属性的类型和Cg中的变量的类型之间的匹配关系 二、Unity提供的内置文件和变量 内置的包含文件 内置的变量 一、如何使用属性 在一开始我们提到过&#xff0c;材质和UnityShader之间有着密切的练习&#xff0c;我们可以通过材质面…

HTML5是什么?与HTML有什么区别?

HTML5 简介 HTML5&#xff08;Hypertext Markup Language, version 5&#xff09;是用于构建和呈现Web内容的最新版本的HTML标准。HTML是一种标记语言&#xff0c;用于描述和定义Web页面的结构和内容。HTML5引入了一系列新的语法、API和特性&#xff0c;旨在增强Web应用的功能…