当前位置: 首页 > 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>通过…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...