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

算法D57 | 动态规划17 | 647. 回文子串 516.最长回文子序列 动态规划总结篇

647. 回文子串   

动态规划解决的经典题目,如果没接触过的话,别硬想 直接看题解。

代码随想录

Python:

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)dp = [[0]*n for _ in range(n)]dp[0] = [1]*nresult = nfor i in range(1, n):for j in range(i,n):if dp[max(0, i-2)][j-1]==1 and s[j]==s[j-i]:dp[i][j] = 1result += 1return result

C++:

class Solution {
public:int countSubstrings(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));dp[0] = vector<int>(s.size(), 1);int result = s.size();for (int i=1; i<s.size(); i++) {for (int j=i; j<s.size(); j++) {if (s[j]==s[j-i] && dp[max(0, i-2)][j-1]==1) {dp[i][j] = 1;result++;}}}return result;}
};

516.最长回文子序列 

647. 回文子串,求的是回文子串,而本题要求的是回文子序列, 大家要搞清楚两者之间的区别。 

代码随想录

Python:

回文子串是连续的,回文子序列是可以不连续的。回文子序列要比求回文子串简单一点,因为情况少了一点,本题的难点在于根据递推关系确定逆向更新。

class Solution:def longestPalindromeSubseq(self, s: str) -> int:n = len(s)dp = [[0]*n for _ in range(n)]for i in range(n):dp[i][i] = 1for i in range(n, -1, -1):for j in range(i+1,n):if s[i]==s[j]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])return dp[0][n-1]

C++:

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));for (int i=0; i<s.size(); i++) dp[i][i] = 1;for (int i=s.size()-1; i>=0; i--) {for (int j=i+1; j<s.size(); j++) {if (s[i]==s[j]) 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][s.size()-1];}
};

动态规划总结篇 

代码随想录

相关文章:

算法D57 | 动态规划17 | 647. 回文子串 516.最长回文子序列 动态规划总结篇

647. 回文子串 动态规划解决的经典题目&#xff0c;如果没接触过的话&#xff0c;别硬想 直接看题解。 代码随想录 Python: class Solution:def countSubstrings(self, s: str) -> int:n len(s)dp [[0]*n for _ in range(n)]dp[0] [1]*nresult nfor i in range(1, n)…...

go的限流

背景 服务请求下游&#xff0c;oom&#xff0c;排查下来发现是一个下游组件qps陡增导致 但是司内网络框架比较挫&#xff0c;竟然不负责框架内存问题&#xff08;有内存管理模块&#xff0c;但逻辑又是无限制使用内存&#xff09; 每个请求一个r、w buffer&#xff0c;请求无限…...

补充--广义表学习

第一章 逻辑结构 &#xff08;1&#xff09;A()&#xff0c;A是一个空表&#xff0c;长度为0&#xff0c;深度为1。 &#xff08;2&#xff09;B(d,e)&#xff0c;B的元素全是原子&#xff0c;d和e&#xff0c;长度为2&#xff0c;深度为1。 &#xff08;3&#xff09;C(b,(c,…...

【笔记】KaiOS SPN显示逻辑

更新流程code 1、gonk/dom/system/gonk/radio/RadioInterfaceLayer.jsm handleNetworkStateChanged -> requestNetworkInfo() -> handleRilResponse的getOperator -> handleOperator handleNetworkStateChanged:网络状态变化请求网络信息 this.requestNetworkInfo…...

Visual Basic6.0零基础教学(4)—编码基础,数据类型与变量

编码基础,数据类型与变量 文章目录 编码基础,数据类型与变量前言一、VB中的编程基础二、VB的基本字符集和词汇集1、字符集2、词汇集 VB中的数据类型VB中的变量与常量一.变量和常量的命名规则二.变量声明1.用Dim语句显式声明变量三. 常量 运算符和表达式一. 运算符 1. 算术运算符…...

VPCFormer:一个基于transformer的多视角指静脉识别模型和一个新基准

文章目录 VPCFormer:一个基于transformer的多视角指静脉识别模型和一个新基准总结摘要介绍相关工作单视角指静脉识别多视角指静脉识别Transformer 数据库基本信息 方法总体结构静脉掩膜生成VPC编码器视角内相关性的提取视角间相关关系提取输出融合IFFN近邻感知模块(NPM) patch嵌…...

Android 图形渲染和显示系统关系

SurfaceFlinger&#xff1a;作为 Android 系统中的一个系统服务&#xff0c;SurfaceFlinger 负责管理整个屏幕的渲染和合成工作。它管理和合成多个 Surface&#xff0c;并与硬件加速器以及 Hardware Composer (HWC) 进行交互&#xff0c;最终将图像数据发送给显示硬件进行显示。…...

3.C++:类与对象(下)

一、再谈构造函数 1.1构造函数体赋值 在创建对象时&#xff0c;编译器通过调用构造函数&#xff0c;给对象中各个成员变量一个合适的初始值。 class Date { public:Date(int year, int month, int day){_year year;_month month;_day day;}private:int _year;int _month;i…...

iOS开发之SwiftUI

iOS开发之SwiftUI 在iOS开发中SwiftUI与Objective-C和Swift不同&#xff0c;它采用了声明式语法&#xff0c;相对而言SwiftUI声明式语法简化了界面开发过程&#xff0c;减少了代码量。 由于SwiftUI是Apple推出的界面开发框架&#xff0c;从iOS13开始引入&#xff0c;Apple使用…...

2024-简单点-pandas

pandas pandas to numpy 尽量不用.values提取数据 numexpr 和 bottleneck加速 布尔操作 describe 自定义describe .pipe df.apply 行或者列级别函数级别应用...

面试笔记——Redis(双写一致、持久化)

双写一致 双写一致性&#xff1a; 当修改了数据库中的数据&#xff0c;也要更新缓存的数据&#xff0c;使缓存和数据库中的数据保持一致。 相关问题&#xff1a;使用Redis作为缓存&#xff0c;mysql的数据如何与Redis进行同步&#xff1f;——双写一致性问题 回答时&#xff0…...

【漏洞复现】科立讯通信指挥调度平台editemedia.php sql注入漏洞

漏洞描述 在20240318之前的福建科立讯通信指挥调度平台中发现了一个漏洞。该漏洞被归类为关键级别,影响文件/api/client/editemedia.php的未知部分。通过操纵参数number/enterprise_uuid可导致SQL注入。攻击可能会远程发起。 免责声明 技术文章仅供参考,任何个人和组织使…...

css的active事件在手机端不生效的解决方法

需求&#xff1a;需求就是实现点击图中的 “抽奖” 按钮&#xff0c;实现一个按钮Q弹的放大缩小动画 上面是实现的效果&#xff0c;pc端&#xff0c;点击触发 :active 问题&#xff1a;但是这种方式在模拟器上可以&#xff0c;真机H5一调试就没生效了&#xff0c;下面是简单…...

00. 认识 Java 语言与安装教程

认识 Java Java 在 20 多年发展过程中&#xff0c;与时俱进&#xff0c;为了适应时代的需要&#xff0c;经历过两次重大的版本升级&#xff0c;一个是 Java 5&#xff0c;它提供了泛型等重要的功能。另一个是提供了 Lambda 表达式等重要的功能的 Java 8。 一些重要的 Java 的…...

数据结构-栈-004

1链栈 1.1栈结点结构体定义 /*定义一个数据结构*/ typedef struct student {char name[32];char sex;int age; }DATA_TYPE;/*定义一个栈结点*/ typedef struct stack_node {DATA_TYPE data;//数据域struct stack_node *pnext;//指针域 }STACK_NODE;1.2栈顶结点结构体定义 /*…...

(第76天)XTTS 升级:11GR2 到 19C

参考文档: 11G - Reduce Transportable Tablespace Downtime using Cross Platform Incremental Backup (Doc ID 1389592.1)V4 使用跨平台增量备份减少可传输表空间的停机时间 (Doc ID 2940565.1)前言 XTTS(Cross Platform Transportable Tablespaces,跨平台迁移表空间)是…...

修改网站源码,给电子商城的商品添加图片时商品id为0的原因

修改网站源码&#xff0c;给电子商城的商品添加图片时商品id为0的原因。花了几个小时查找原因。后来&#xff0c;由于PictureControl.class.php是复制CourseControl.class.php而来&#xff0c;于是对比了这两个文件&#xff0c;在CourseControl.class.php找到了不一样的关键几条…...

ffmpeg开发异步AI推理Filter

ffmpeg开发异步AI推理Filter 1.环境搭建、推理服务及客户端SDK2.编译原版ffmpeg3.测试原版ffmpeg的filter功能4.准备异步推理filter5.修改点6.重新编译ffmpeg7.测试异步推理filter本文旨在阐述如何开发一个FFmpeg Filter,该模块利用gRPC异步通信机制调用远程视频处理服务。这一…...

python与excel第七节 拆分工作簿

一个工作簿中多个工作表拆分为多个工作簿 假设一个excle工作簿中有多个工作表&#xff0c;现在需要将每个工作表拆分为单独的工作簿。 例子&#xff1a; import xlwings as xw# 设置生成文件的路径path D:\\TEST\\dataIn# 源文件的路径workbook_name D:\\TEST\\dataIn\\产…...

JS08-DOM节点完整版

DOM节点 查找节点 父节点 <div class="father"><div class="son">儿子</div></div><script>let son = document.querySelector(.son)console.log(son.parentNode);son.parentNode.style.display = none</script>通过…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...