当前位置: 首页 > 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; 了解当前服务器的网络接口信息…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...