【LeetCode】516. 最长回文子序列
文章目录
- 1. 思路讲解
- 1.1 创建dp表
- 1.2 状态转移方程
- 1.3 不需考虑边界问题
- 2. 整体代码
1. 思路讲解
1.1 创建dp表
此题采用动态规划的方法,创建一个二维dp表,dp[i][j]表示s[i, j]中最大回文子序列的长度。且我们人为规定 i 是一定小于等于 j 的。
1.2 状态转移方程
在求dp[i][j]时,首先要判断s[i]和s[j]是否相同。
如果 s[i] == s[j]
- 如果 i == j,说明 i 与 j 的位置相同,此时dp[i][j] 就为 1
- 如果 i + 1 == j,说明 i 与 j 相邻,此时dp[i][j] 就为2
- 其他情况下,说明 i 和 j 中间有其他元素,那么此时dp[i][j] = dp[i+1][j-1] + 2;
如果s[i] != s[j]
那么此时,说明不能同时以 i 为开头和以 j 为结尾,我们去掉这种情况寻找一个最大子序列即可。方法就是在 dp[i+1, j] 和 dp[i, j-1] 中选一个最大的即可。即dp[i][j] = max(dp[i+1[j], dp[i][j-1]);
1.3 不需考虑边界问题
在求dp[i][j]的时候,我们可能会用到 i + 1 和 j - 1,在它们有可能越界的时候,一定是 i 等于 j 的时候。我们创建的dp表是二维的,我们可以想到,在可能越界的时候,就是左上角的位置或者右下角的位置,但其实这两个位置满足 i == j,那么dp[i][j] 就会被直接赋值为1,此时就不会用到 i + 1 和 j - 1 了,所以其实我们不用考虑越界的情况。
2. 整体代码

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();// 创建二维dp表,dp[i][j]表示s[i, j]最大子序列的长度vector<vector<int>> dp(n, vector<int>(n));// dp[i][j]需要用到dp[i+1][j-1]// 所以i从大到小循环,j从小到大循环,且i是小于等于j的for (int j = 0; j < n; ++j){for (int i = j; i >= 0; --i){if (s[i] == s[j]){if (i == j) dp[i][j] = 1;else if (i + 1 == j) dp[i][j] = 2;else 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];}
};
相关文章:
【LeetCode】516. 最长回文子序列
文章目录 1. 思路讲解1.1 创建dp表1.2 状态转移方程1.3 不需考虑边界问题 2. 整体代码 1. 思路讲解 1.1 创建dp表 此题采用动态规划的方法,创建一个二维dp表,dp[i][j]表示s[i, j]中最大回文子序列的长度。且我们人为规定 i 是一定小于等于 j 的。 1.2…...
Java 集合框架
Java 集合框架提供了一组接口和类,以实现各种数据结构和算法。 集合框架满足以下几个要求。 该框架必须是高性能的。基本集合(动态数组,链表,树,哈希表)的实现也必须是高效的。 该框架允许不同类型的集合…...
遇到多人协作,我们该用git如何应对?(版本二)
一、多人协作二 1.1多人协作 一般情况下,如果有多需求需要多人同时进行开发,是不会在一个分支上进行多人开发,而是一个需求或一个功能点就要创建一个feature 分支。 现在同时有两个需求需要你和你的小伙伴进行开发,那么你们俩便…...
Flutter iOS 集成使用 fluter boost
在 Flutter项目中集成完 flutter boost,并且已经使用了 flutter boost进行了路由管理,这时如果需要和iOS混合开发,这时就要到 原生端进行集成。 注意:之前建的项目必须是 Flutter module项目,并且原生项目和flutter m…...
node.js相关的npm包的集合
一、实用功能 1. qs 一个简单易用的字符串解析和格式化库 2.rxjs RxJS是一组模块化的库,用于使用 JavaScript 中的可观察集合和组合来组合异步和基于事件的程序。 3. mitt 微型 200b 功能事件发射器/发布订阅. 4.Underscore.js Underscore.js是一个用于 JavaScript…...
Android Ble蓝牙App(二)连接与发现服务
Ble蓝牙App(二)连接与发现服务 前言正文一、GATT回调二、连接和断连三、连接状态回调四、发现服务五、服务适配器六、显示服务七、源码 前言 在上一篇中我们进行扫描设备的处理,本文中进行连接和发现服务的数据处理,运行效果图如下…...
Android 自定义按钮(可滑动、点击)
按钮图片素材 https://download.csdn.net/download/Lan_Se_Tian_Ma/88151085 px 和 dp 转换工具类(Java) // px 和 dp 转换工具类 public class DensityUtil {/*** 根据手机的分辨率从 dip 的单位 转成为 px(像素)*/public static int dip2px(Conte…...
mac录屏怎么打开?很简单,让我来教你!
mac电脑作为一款广受欢迎的电脑系统,提供了多种方式来满足用户录屏的需求。无论您是要录制教学视频、制作演示文稿,还是记录游戏精彩瞬间,mac电脑都能帮助您实现这些目标。本文将为您介绍两种mac录屏的方法。通过本文的指导,您将能…...
Stable Diffusion AI绘画学习指南【插件安装设置】
插件安装的方式 可用列表方式安装,点开Extensions 选项卡,找到如下图,找到Available选项卡,点load from加载可用插件,在可用插件列表中找到要装的插件按install 按扭按装,安装完后(Apply and restart UI)应…...
APP开发中的性能优化:提升用户满意度的关键
APP开发中的性能优化是需要持续进行的,它不仅能够让用户体验到 APP的使用感受,还能在一定程度上提升用户的满意度,从而提升 APP的粘性和转化率。不过在实际开发中,很多 APP开发公司会存在性能优化上的问题,这就需要了解…...
Golang 切片 常用方法
文章目录 移除指定位置的元素查找元素的位置查找最大最小的元素去重随机打乱排序二维排序sort.Sort 排序 下面的方法省略一些校验,如数组越界等,且都采用泛型(要求go版本 > 1.18) 移除指定位置的元素 package mainimport ("fmt" )func Del…...
【Linux后端服务器开发】poll/epoll多路转接IO服务器
目录 一、poll原理 二、poll实现多路转接IO服务器 三、epoll函数接口 四、epoll的工作原理 五、epoll实现多路转接IO服务器 一、poll原理 poll函数接口 #include <poll.h> int poll(struct pollfd *fds, nfds_t nfds, int timeout);// pollfd结构 struct pollfd …...
【设计模式——学习笔记】23种设计模式——命令模式Command(原理讲解+应用场景介绍+案例介绍+Java代码实现)
文章目录 案例引入介绍基础介绍登场角色 案例实现案例一实现 案例二介绍实现拓展 命令模式在JdbcTemplate源码中的应用总结文章说明 案例引入 有一套智能家电,其中有照明灯、风扇、冰箱、洗衣机,这些智能家电来自不同的厂家,我们不想针对每一…...
Rust中的高吞吐量流处理
本篇文章主要介绍了Rust中流处理的概念、方法和优化。作者不仅介绍了流处理的基本概念以及Rust中常用的流处理库,还使用这些库实现了一个流处理程序。 最后,作者介绍了如何通过测量空闲和阻塞时间来优化流处理程序的性能,并将这些内容同步至…...
探索编程世界的宝藏:程序员必掌握的20大算法
文章目录 1 引言2 冒泡排序算法:编程世界的排序魔法 🧙♀️🔢3 选择排序算法:排序世界的精确挑选器 🎯🔢4 插入排序算法:排序世界的巧妙插珠者 ✨🔢5 快速排序算法:排序…...
Android NFC通信示例
前言 近距离无线通信 (NFC) 是一组近距离无线技术,通常只有在距离不超过 4 厘米时才能启动连接。借助 NFC,您可以在 NFC 标签与 Android 设备之间或者两台 Android 设备之间共享小型负载。 支持 NFC 的 Android 设备同时支持以下三种主要操作模式&…...
2023年08月IDE流行度最新排名
点击查看最新IDE流行度最新排名(每月更新) 2023年08月IDE流行度最新排名 顶级IDE排名是通过分析在谷歌上搜索IDE下载页面的频率而创建的 一个IDE被搜索的次数越多,这个IDE就被认为越受欢迎。原始数据来自谷歌Trends 如果您相信集体智慧&am…...
使用Beego和MySQL实现帖子和评论的应用,并进行接口测试(附源码和代码深度剖析)
文章目录 小项目介绍源码分析main.gorouter.gomodels/user.gomodels/Post.gomodels/comment.gocontrollers/post.gocontrollers/comment.go 接口测试测试增加帖子测试查看帖子测试增加评论测试查看评论 小项目介绍 经过对需求的分析,我增加了一些额外的东西&#x…...
物联网潜在的巨大价值在于大数据分析
物联网潜在的巨大价值在于大数据分析 从数据里去挖掘市场或者用户的精准需求。 往小的说,后台可以统计用户家里各各插座一年甚至更久的用电情况,这些数据也可以通过app或者小程序展现给用户。 用户可以很直观看到自己一年的用电情况,哪个家…...
SSL原理详解
SSL协议结构: SSL协议分为两层,下层为SSL记录协议,上层为SSL握手协议、SSL密码变化协议和SSL警告协议。 1.下层为SSL记录协议,主要作用是为高层协议提供基本的安全服务 建立在可靠的传输之上,负责对上层的数据进行分块…...
常见音视频编码二进制分析笔记(H264,H265,AAC,OPUS,G711A,G711U)
常见音视频编码二进制分析笔记 文章目录常见音视频编码二进制分析笔记视频H.264 (AVC)说明nal_unit_type:nal_ref_idcH.265 (HEVC)音频AAC (Advanced Audio Coding)G.711A (PCMA)G.711U (PCMU)OPUS视频 H.264 (AVC) 标准来源:ITU-T H.264 | ISO/IEC 14496-10 起始…...
百度网盘直链解析:突破限速实现10倍下载加速的终极指南
百度网盘直链解析:突破限速实现10倍下载加速的终极指南 【免费下载链接】baidu-wangpan-parse 获取百度网盘分享文件的下载地址 项目地址: https://gitcode.com/gh_mirrors/ba/baidu-wangpan-parse 在当今数字化时代,百度网盘已成为国内用户最常用…...
Loom不是银弹!Java工程师必须掌握的4层响应式适配模型(含线程模型迁移决策树)
第一章:Loom不是银弹!Java工程师必须掌握的4层响应式适配模型(含线程模型迁移决策树)Loom 的虚拟线程极大缓解了阻塞式 I/O 的资源开销,但它无法自动将传统回调式或事件驱动的响应式代码(如 Project Reacto…...
DIY蝶形激光器驱动:从零开始搭建窄脉冲种子源控制系统(附详细参数配置)
DIY蝶形激光器驱动:从零开始搭建窄脉冲种子源控制系统 在电子爱好者和激光技术初学者的世界里,能够亲手搭建一套完整的蝶形激光器驱动系统无疑是一项极具挑战性和成就感的项目。不同于市面上现成的商业产品,DIY方案不仅能让你深入理解激光器的…...
Bilibili API评论接口终极调用指南:5个高效数据获取技巧
Bilibili API评论接口终极调用指南:5个高效数据获取技巧 【免费下载链接】bilibili-api 哔哩哔哩常用API调用。支持视频、番剧、用户、频道、音频等功能。原仓库地址:https://github.com/MoyuScript/bilibili-api 项目地址: https://gitcode.com/gh_mi…...
MindSpore 环境配置完全指南安
前面我们对 Kafka 的整体架构和一些关键的概念有了一个基本的认知,本文主要介绍 Kafka 的一些配置参数。掌握这些参数的作用对我们的运维和调优工作还是非常有帮助的。 写在前面 Kafka 作为一个成熟的事件流平台,有非常多的配置参数。详细的参数列表可以…...
Java生产者消费者模式实战解析
Java生产者消费者模式实战解析异步模式传统版改进版阻塞队列异步模式 传统版 异步模式之生产者/消费者: class ShareData {private int number 0;private Lock lock new ReentrantLock();private Condition condition lock.newCondition();public void increm…...
# 英伟达AI实验室财经分析报告(2026)
2026财年整体业绩 总营收:2159.38亿美元,同比增长65% 净利润:1200.67亿美元,同比增长65%,日均净赚约3.3亿美元 毛利率:稳定在75%的行业天花板水平,非GAAP毛利率达75.2% 市值:截至202…...
Qt新手必看:MinGW和MSVC构建套件到底怎么选?从安装到项目配置保姆级指南
Qt构建套件选择指南:MinGW与MSVC深度对比与实战配置 第一次打开Qt Creator时,那个充满选项的"Kit Selection"界面总让人望而生畏。作为一个从零开始学习Qt的开发者,我也曾在这个界面前犹豫不决——MinGW还是MSVC?这个看…...
Fluent计算总发散?别急着重画网格,先检查这5个隐藏设置(附诊断命令)
Fluent计算总发散?别急着重画网格,先检查这5个隐藏设置(附诊断命令) 凌晨三点,屏幕上的残差曲线突然像过山车一样飙升,你盯着"floating point exception"的报错提示,咖啡杯悬在半空—…...
