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

516.最长回文子序列

刷算法题:

第一遍:1.看5分钟,没思路看题解

2.通过题解改进自己的解法,并且要写每行的注释以及自己的思路。

3.思考自己做到了题解的哪一步,下次怎么才能做对(总结方法)

4.整理到自己的自媒体平台。

5.再刷重复的类似的题目,根据时间和任务安排刷哪几个板块

6.用c++语言 都刷过一遍了 就刷中等

一.题目

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

示例 2:

输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。

提示:

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

二、反思

1.自己的解法

2.题目的解法 

class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.length();vector<vector<int>> dp(n,vector<int>(n));//dp【i】【j】是i到j的最长子序列。for(int i=n-1;i>=0;i--){dp[i][i]=1;int c1=s[i];for(int j=i+1;j<n;j++){//只要是子序列这么做不断向后遍历,就等于删除了。int c2=s[j];if(c1==c2){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][n-1];}
};

 3.思路的异同

对于一个子序列而言,如果它是回文子序列,并且长度大于 2,那么将它首尾的两个字符去除之后,它仍然是个回文子序列。因此可以用动态规划的方法计算给定字符串的最长回文子序列。

用 dp[i][j] 表示字符串 s 的下标范围 [i,j] 内的最长回文子序列的长度。假设字符串 s 的长度为 n,则只有当 0≤i≤j<n 时,才会有 dp[i][j]>0,否则 dp[i][j]=0。(这里就强调了for遍历顺序)

由于任何长度为 1 的子序列都是回文子序列,因此动态规划的边界情况是,对任意 0≤i<n,都有 dp[i][i]=1。

当 i<j 时,计算 dp[i][j] 需要分别考虑 s[i] 和 s[j] 相等和不相等的情况:

如果 s[i]=s[j],则首先得到 s 的下标范围 [i+1,j−1] 内的最长回文子序列,然后在该子序列的首尾分别添加 s[i] 和 s[j],即可得到 s 的下标范围 [i,j] 内的最长回文子序列,因此 dp[i][j]=dp[i+1][j−1]+2;

如果 s[i]=s[j],则 s[i] 和 s[j] 不可能同时作为同一个回文子序列的首尾,因此 dp[i][j]=max(dp[i+1][j],dp[i][j−1])。

由于状态转移方程都是从长度较短的子序列向长度较长的子序列转移,因此需要注意动态规划的循环顺序。

最终得到 dp[0][n−1] 即为字符串 s 的最长回文子序列的长度。

三.进步的地方

 上一段直接封神

相关文章:

516.最长回文子序列

刷算法题&#xff1a; 第一遍&#xff1a;1.看5分钟&#xff0c;没思路看题解 2.通过题解改进自己的解法&#xff0c;并且要写每行的注释以及自己的思路。 3.思考自己做到了题解的哪一步&#xff0c;下次怎么才能做对(总结方法) 4.整理到自己的自媒体平台。 5.再刷重复的类…...

leetcode hot100【LeetCode 114.二叉树展开为链表】java实现

LeetCode 114.二叉树展开为链表 题目描述 给你二叉树的根结点 root &#xff0c;请你将它展开为一个单链表&#xff1a; 展开后的单链表应该同样使用 TreeNode &#xff0c;其中 right 子指针指向链表中下一个结点&#xff0c;而左子指针始终为 null 。 展开后的单链表应该与…...

SpringMVC学习记录(二)之接收数据

SpringMVC学习记录&#xff08;二&#xff09;之接收数据 一、快速搭建SpringMVC框架1、配置分析2、准备项目3、Controller声明4、Spring MVC核心组件配置类5、SpringMVC环境搭建6、启动测试 二、SpringMVC接收数据1、访问路径设置1&#xff09;精准路径匹配2&#xff09;模糊路…...

C语言串讲-3之函数和数组

1&#xff0e;函数名是一个指针&#xff0c;保存函数地址入口。函数名是函数的入口地址。函数的入口地址称为函数指针。 2&#xff0e;传参--本质是创建副本 &#xff08;1&#xff09;实参与形参 &#xff08;2&#xff09;值传递&#xff0c;指针传递&#xff0c;引用传递 …...

设计模式-状态模式(State)

允许一个对象内部状态改变时改变它的行为&#xff0c;对象看起来似乎修改了它的类 问题&#xff1a; 状态模式和有限状态机紧密相关。其主要思想是程序在任意时刻仅可处于几种有限的状态中。 在任何一个特定状态中&#xff0c; 程序的行为都不相同&#xff0c; 且可瞬间从一个…...

c语言中的文件操作(2)

文件的打开-fopen 函数介绍 文件的打开方式 相对路径与绝对路径 文件关闭函数fclose 文件操作的正确流程 函数的介绍 文件的打开形式 相对路径与绝对路径 文件的关闭函数-fclose 正确的文件操作的流程 前言 通过前面的章节我们已经知道文件的基本的概念&#xff0c;我们如…...

【Verilog】case、casex、casez的区别

在case语句中&#xff0c;敏感表达式中与各项值之间的比较是一种全等比较&#xff0c;每一位都相同才认为匹配。 在casez语句中&#xff0c;如果分支表达式某些位的值为高阻z&#xff0c;那么对这些位的比较就会忽略&#xff0c;不予考虑&#xff0c;而只关注其他位的比较结果…...

Seata源码笔记(二)

Seata源码笔记&#xff08;二&#xff09; 配置相关的ConfigurationFactory静态代码块load()&#xff1a;融入spring获取value的方式Configuration的get方法拦截后&#xff0c;value取值优先级ObjectHolderPROPERTY_BEAN_MAP getInstancebuildConfiguration reload 基于incubar…...

【Java SE】接口类型

在 Java 中&#xff0c;接口&#xff08;Interface&#xff09;是一种引用类型&#xff0c;类似于特殊的抽象类&#xff0c;用于定义一组方法规范&#xff0c;而不提供具体的实现。接口可以包含成员属性&#xff0c;这些属性默认是常量。尽管每个类只能继承一个父类&#xff0c…...

[代码随想录Day10打卡] 理论基础 232.用栈实现队列 225. 用队列实现栈 20. 有效的括号 1047. 删除字符串中的所有相邻重复项

理论基础 队列先入先出。 栈先入后出。 具体的实现和用法根据语言的不同而不同。 参考的文章 https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 232.用栈实现队列 这个定义入栈和出栈&#xff0c;往队列中加入…...

redis:RDB和AOF机制

个人主页 &#xff1a; 个人主页 个人专栏 &#xff1a; 《数据结构》 《C语言》《C》《Linux》《网络》 《redis学习笔记》 文章目录 前言RDBAOF总结 前言 redis是一个内存数据库&#xff0c;把数据存储在内存中的&#xff0c;而内存中的数据是不持久的&#xff0c;要想能够做…...

券商隔夜单自动下单交易接口

之前研究打板排板&#xff0c;研究怎么才能买得进去。 最近遇到几只利空跌停板&#xff0c;缩量跌停&#xff0c;明天大概率继续一字封板跌停。 如果卖不掉&#xff0c;意味着还要继续吃几个跌停&#xff0c;甚至ST票十几个跌停都有可能。 一次跌停亏几万&#xff0c;还是挺…...

生成任意3D和4D场景!GenXD:通用3D-4D联合生成框架 | 新加坡国立微软

文章链接: https://arxiv.org/pdf/2411.02319 项目链接&#xff1a;https://gen-x-d.github.io/ 有视频 亮点直击 设计了一个数据整理流程&#xff0c;从视频中获取包含可移动物体的高质量4D数据&#xff0c;并为30,000个视频标注了相机姿态。这个大规模数据集称为CamVid-30K&…...

通过命令学习k8s

1、kubectl 命令可以列出所有命令 2、kubectl version 命令可以查看版本号 3、kubectl cluster-info命令可以查看集群信息&#xff08;192.168.218.136:6443 即为kube-apiserver的IP和端口。&#xff09; [rootk8s-master ~]# kubectl cluster-info Kubernetes master is run…...

【redis】—— 初识redis(redis基本特征、应用场景、以及重大版本说明)

序言 本文将引导读者探索Redis的世界&#xff0c;深入了解其发展历程、丰富特性、常见应用场景、使用技巧等&#xff0c;最后会对Redis演进过程中具有里程碑意义的版本进行详细解读。 &#xff08;一&#xff09;初始redis Redis是一种基于键值对&#xff08;key-value&#x…...

服务器显卡和桌面pc显卡有什么不同

服务器显卡和桌面 PC 显卡在设计目标、性能优化、功能支持和硬件规格上都有显著不同。以下是主要区别&#xff1a; 1. 设计用途 服务器显卡&#xff1a;主要用于计算、深度学习、数据分析、科学计算、虚拟化和图形渲染等任务。其设计目标是持续高负载计算&#xff0c;保证高稳…...

Chrome使用IE内核

Chrome使用IE内核 1.下载扩展程序IE Tab 2.将下载好的IE Tab扩展程序拖拽到扩展程序界面&#xff0c;之后重启chrome浏览器即可...

类和对象(C++)——默认成员函数,构造函数,析构函数

1. 类的默认成员函数 默认成员函数就是用户没有显式实现&#xff0c;编译器会⾃动⽣成的成员函数称为默认成员函数。⼀个类&#xff0c;不写的情况下编译器会默认生成以下6个默认成员函数&#xff0c;需要注意的是这6个中最重要的是前4个&#xff0c;最后两个取地址重载&#…...

深入理解 Vue v-model 原理与应用

一、引言 在 Vue.js 开发中,v-model是一个非常重要且强大的指令。它为开发者在处理表单输入和数据双向绑定等场景中提供了极大的便利。无论是新手还是有经验的开发者,深入理解v-model对于高效地构建 Vue 应用至关重要。本文将对v-model进行深入剖析,从其基本原理、使用方式…...

内网域环境、工作组、局域网等探针方案

1. 信息收集 1.1 网络收集 了解当前服务器的计算机基本信息&#xff0c;为后续判断服务器角色&#xff0c;网络环境做准备 systeminfo 详细信息 net start 启动服务 tasklist 进程列表 schtasks 计划任务&#xff08;受权限影响&#xff09; 了解当前服务器的网络接口信息…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...