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

【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]

  1. 如果 i == j,说明 i 与 j 的位置相同,此时dp[i][j] 就为 1
  2. 如果 i + 1 == j,说明 i 与 j 相邻,此时dp[i][j] 就为2
  3. 其他情况下,说明 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表 此题采用动态规划的方法&#xff0c;创建一个二维dp表&#xff0c;dp[i][j]表示s[i, j]中最大回文子序列的长度。且我们人为规定 i 是一定小于等于 j 的。 1.2…...

Java 集合框架

Java 集合框架提供了一组接口和类&#xff0c;以实现各种数据结构和算法。 集合框架满足以下几个要求。 该框架必须是高性能的。基本集合&#xff08;动态数组&#xff0c;链表&#xff0c;树&#xff0c;哈希表&#xff09;的实现也必须是高效的。 该框架允许不同类型的集合…...

遇到多人协作,我们该用git如何应对?(版本二)

一、多人协作二 1.1多人协作 一般情况下&#xff0c;如果有多需求需要多人同时进行开发&#xff0c;是不会在一个分支上进行多人开发&#xff0c;而是一个需求或一个功能点就要创建一个feature 分支。 现在同时有两个需求需要你和你的小伙伴进行开发&#xff0c;那么你们俩便…...

Flutter iOS 集成使用 fluter boost

在 Flutter项目中集成完 flutter boost&#xff0c;并且已经使用了 flutter boost进行了路由管理&#xff0c;这时如果需要和iOS混合开发&#xff0c;这时就要到 原生端进行集成。 注意&#xff1a;之前建的项目必须是 Flutter module项目&#xff0c;并且原生项目和flutter m…...

node.js相关的npm包的集合

一、实用功能 1. qs 一个简单易用的字符串解析和格式化库 2.rxjs RxJS是一组模块化的库&#xff0c;用于使用 JavaScript 中的可观察集合和组合来组合异步和基于事件的程序。 3. mitt 微型 200b 功能事件发射器/发布订阅. 4.Underscore.js Underscore.js是一个用于 JavaScript…...

Android Ble蓝牙App(二)连接与发现服务

Ble蓝牙App&#xff08;二&#xff09;连接与发现服务 前言正文一、GATT回调二、连接和断连三、连接状态回调四、发现服务五、服务适配器六、显示服务七、源码 前言 在上一篇中我们进行扫描设备的处理&#xff0c;本文中进行连接和发现服务的数据处理&#xff0c;运行效果图如下…...

Android 自定义按钮(可滑动、点击)

按钮图片素材 https://download.csdn.net/download/Lan_Se_Tian_Ma/88151085 px 和 dp 转换工具类&#xff08;Java&#xff09; // px 和 dp 转换工具类 public class DensityUtil {/*** 根据手机的分辨率从 dip 的单位 转成为 px(像素)*/public static int dip2px(Conte…...

mac录屏怎么打开?很简单,让我来教你!

mac电脑作为一款广受欢迎的电脑系统&#xff0c;提供了多种方式来满足用户录屏的需求。无论您是要录制教学视频、制作演示文稿&#xff0c;还是记录游戏精彩瞬间&#xff0c;mac电脑都能帮助您实现这些目标。本文将为您介绍两种mac录屏的方法。通过本文的指导&#xff0c;您将能…...

Stable Diffusion AI绘画学习指南【插件安装设置】

插件安装的方式 可用列表方式安装&#xff0c;点开Extensions 选项卡&#xff0c;找到如下图&#xff0c;找到Available选项卡&#xff0c;点load from加载可用插件&#xff0c;在可用插件列表中找到要装的插件按install 按扭按装&#xff0c;安装完后(Apply and restart UI)应…...

APP开发中的性能优化:提升用户满意度的关键

APP开发中的性能优化是需要持续进行的&#xff0c;它不仅能够让用户体验到 APP的使用感受&#xff0c;还能在一定程度上提升用户的满意度&#xff0c;从而提升 APP的粘性和转化率。不过在实际开发中&#xff0c;很多 APP开发公司会存在性能优化上的问题&#xff0c;这就需要了解…...

Golang 切片 常用方法

文章目录 移除指定位置的元素查找元素的位置查找最大最小的元素去重随机打乱排序二维排序sort.Sort 排序 下面的方法省略一些校验&#xff0c;如数组越界等&#xff0c;且都采用泛型(要求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源码中的应用总结文章说明 案例引入 有一套智能家电&#xff0c;其中有照明灯、风扇、冰箱、洗衣机&#xff0c;这些智能家电来自不同的厂家&#xff0c;我们不想针对每一…...

Rust中的高吞吐量流处理

本篇文章主要介绍了Rust中流处理的概念、方法和优化。作者不仅介绍了流处理的基本概念以及Rust中常用的流处理库&#xff0c;还使用这些库实现了一个流处理程序。 最后&#xff0c;作者介绍了如何通过测量空闲和阻塞时间来优化流处理程序的性能&#xff0c;并将这些内容同步至…...

探索编程世界的宝藏:程序员必掌握的20大算法

文章目录 1 引言2 冒泡排序算法&#xff1a;编程世界的排序魔法 &#x1f9d9;‍♀️&#x1f522;3 选择排序算法&#xff1a;排序世界的精确挑选器 &#x1f3af;&#x1f522;4 插入排序算法&#xff1a;排序世界的巧妙插珠者 ✨&#x1f522;5 快速排序算法&#xff1a;排序…...

Android NFC通信示例

前言 近距离无线通信 (NFC) 是一组近距离无线技术&#xff0c;通常只有在距离不超过 4 厘米时才能启动连接。借助 NFC&#xff0c;您可以在 NFC 标签与 Android 设备之间或者两台 Android 设备之间共享小型负载。 支持 NFC 的 Android 设备同时支持以下三种主要操作模式&…...

2023年08月IDE流行度最新排名

点击查看最新IDE流行度最新排名&#xff08;每月更新&#xff09; 2023年08月IDE流行度最新排名 顶级IDE排名是通过分析在谷歌上搜索IDE下载页面的频率而创建的 一个IDE被搜索的次数越多&#xff0c;这个IDE就被认为越受欢迎。原始数据来自谷歌Trends 如果您相信集体智慧&am…...

使用Beego和MySQL实现帖子和评论的应用,并进行接口测试(附源码和代码深度剖析)

文章目录 小项目介绍源码分析main.gorouter.gomodels/user.gomodels/Post.gomodels/comment.gocontrollers/post.gocontrollers/comment.go 接口测试测试增加帖子测试查看帖子测试增加评论测试查看评论 小项目介绍 经过对需求的分析&#xff0c;我增加了一些额外的东西&#x…...

物联网潜在的巨大价值在于大数据分析

物联网潜在的巨大价值在于大数据分析 从数据里去挖掘市场或者用户的精准需求。 往小的说&#xff0c;后台可以统计用户家里各各插座一年甚至更久的用电情况&#xff0c;这些数据也可以通过app或者小程序展现给用户。 用户可以很直观看到自己一年的用电情况&#xff0c;哪个家…...

SSL原理详解

SSL协议结构&#xff1a; SSL协议分为两层&#xff0c;下层为SSL记录协议&#xff0c;上层为SSL握手协议、SSL密码变化协议和SSL警告协议。 1.下层为SSL记录协议&#xff0c;主要作用是为高层协议提供基本的安全服务 建立在可靠的传输之上&#xff0c;负责对上层的数据进行分块…...

3分钟解锁B站缓存视频:m4s-converter无损转换指南

3分钟解锁B站缓存视频&#xff1a;m4s-converter无损转换指南 【免费下载链接】m4s-converter 一个跨平台小工具&#xff0c;将bilibili缓存的m4s格式音视频文件合并成mp4 项目地址: https://gitcode.com/gh_mirrors/m4/m4s-converter 你是否曾为B站下架的视频感到惋惜&…...

利用叉乘判断OpenGL中的左右关系

在 OpenGL 中&#xff0c;判断一个点或向量相对于另一个向量&#xff08;如视线方向或边&#xff09;的“左右关系”&#xff0c;本质上是一个空间方位判定问题。其核心方法是利用叉乘&#xff08;Cross Product&#xff09;的几何特性&#xff0c;结合坐标系的手性规则来实现。…...

华为ENSP模拟器实战:手把手教你从零搭建一个可用的企业级无线网络(AC+AP+交换机)

华为ENSP模拟器实战&#xff1a;从零构建企业级无线网络的完整指南 1. 环境准备与基础概念 在开始构建企业级无线网络之前&#xff0c;我们需要先理解几个核心组件的作用。华为的无线控制器(AC)负责集中管理所有接入点(AP)&#xff0c;而交换机则负责连接这些设备并提供必要的V…...

AI Linux运维——项目部署(一)

一、项目介绍 中州养老系统为养老院量身定制开发专业的养老管理软件产品&#xff1b;涵盖来访管理、入退管理、在住管理、服务管理 、财务管理等功能模块&#xff0c;涉及从来访参观到退住办理的完整流程。 项目原型访问地址&#xff1a;https://codesign.qq.com/s/45927762406…...

猫抓Cat-Catch:三步搞定网页视频音频下载的终极指南

猫抓Cat-Catch&#xff1a;三步搞定网页视频音频下载的终极指南 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 还在为无法保存喜欢的在线视频而烦…...

别光看部署了!用Minikube在Win11本地实战K8s Service:NodePort vs LoadBalancer 到底怎么选?

在Windows11本地Minikube集群中实战&#xff1a;NodePort与LoadBalancer服务类型深度对比 当你在本地Minikube集群中成功部署了第一个应用后&#xff0c;如何将服务暴露给外部访问就成了下一个需要解决的问题。Kubernetes提供了多种服务类型&#xff0c;其中NodePort和LoadBala…...

告别Blob分析:Halcon差异化模型在复杂印刷品检测中的降维打击

印刷品缺陷检测的技术革命&#xff1a;Halcon差异化模型实战解析 当产线上每分钟流过数百个印刷品时&#xff0c;传统Blob分析就像用放大镜检查跑车——方法没错&#xff0c;但工具完全跟不上节奏。键盘字符检测这类高精度场景中&#xff0c;0.1mm的油墨缺失或1个像素的异物都可…...

ApiPost实战指南:从接口创建到团队协作的全流程解析

1. 从零开始创建你的第一个接口 刚接触ApiPost时&#xff0c;我最先被它的简洁界面吸引。作为一款国产的API开发工具&#xff0c;它完美解决了我们团队在接口调试和文档管理上的痛点。下面我就用最直白的方式&#xff0c;带你走完创建接口的全流程。 打开ApiPost后&#xff0c;…...

【2026年最新600套毕设项目分享】基于微信小程序的童装商城(30023)

有需要的同学&#xff0c;源代码和配套文档领取&#xff0c;加文章最下方的名片哦 一、项目演示 项目演示视频 二、资料介绍 完整源代码&#xff08;前后端源代码SQL脚本&#xff09;配套文档&#xff08;LWPPT开题报告/任务书&#xff09;远程调试控屏包运行一键启动项目&…...

2026奇点大会唯一指定技术白皮书节选:AI-Native Runtime如何重构云原生内核?(含eBPF+MoE调度器实测性能对比)

第一章&#xff1a;2026奇点智能技术大会&#xff1a;AI原生云原生融合 2026奇点智能技术大会(https://ml-summit.org) 本届大会首次提出“AI原生云原生融合”范式&#xff0c;标志着基础设施层与智能层的深度耦合进入工程化落地阶段。传统云原生以容器、微服务、声明式API为…...