记忆化搜索和动态规划 --最长回文子串为例
记忆化搜索
记忆化搜索是一种优化递归算法的方法,通过将已经计算过的子问题的结果存储起来(通常使用哈希表或数组),避免重复计算相同的子问题。
本质上是通过缓存中间结果来减少计算的重复性。
动态规划
动态规划是通过将问题分解成子问题来解决的,它通常通过表格化的方式(自底向上)来存储子问题的解,以便在需要时能够快速访问。
动态规划的核心思想是通过自底向上的方式来解决问题,通常使用一个数组或表格来存储每个子问题的解,从而避免了递归的重复计算。
二者区别与联系
记忆化搜索和动态规划的区别,主要在于计算的顺序。
记忆化搜索通常是自顶向下的递归方式,在递归中检查子问题是否已经计算过,并存储结果。
动态规划通常是自底向上的方式,逐步计算所有子问题,并存储所有的中间结果,最终得到问题的解。
两者的时间复杂度是相同的,都是 O(n),因为两者都避免了重复计算子问题。
例题
最长回文子串 -力扣
记忆化搜索解答:
class Solution {
public:int dp[1000][1000];std::string ss;bool judge(int l, int r) {if (dp[l][r] != -1) {return dp[l][r];}if (ss[l] == ss[r]) {if (r - l > 1) {if (dp[l + 1][r - 1] == -1) {dp[l][r] = judge(l + 1, r - 1);} else {dp[l][r] = dp[l + 1][r - 1];}} else {dp[l][r] = 1;}} else {dp[l][r] = 0;}return dp[l][r];}std::string longestPalindrome(std::string s) {memset(dp,-1,sizeof(dp));int len = s.length();ss = s;int res = 0;int l = 0;for (int i = 0; i < len; i++) {for (int j = i; j < len; j++) {dp[i][j] = judge(i, j);if (dp[i][j] == 1 && j - i > res) {res = j - i;l = i;}}}return s.substr(l, res + 1);}
};
动态规划解答
class Solution {
public:std::string longestPalindrome(std::string s) {int len = s.length();bool dp[1000][1000];memset(dp,false,sizeof(dp));for(int i = len - 1; i >= 0; i--){for(int j = i; j < len; j++){if(s[i] != s[j]){dp[i][j] = false;}else{if(i == j){dp[i][j] = true;}else{if(j - i == 1){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}}}}int res = 0;int l = 0;for(int i = 0; i < len; i++){for(int j = i; j < len; j++){if(dp[i][j] == true){if(res < j - i){res = j - i;l = i;}}}}return s.substr(l,res + 1);}};
由于函数调用的原因,使用递归的记忆化搜索算法的时间会稍微久一点
相关文章:
记忆化搜索和动态规划 --最长回文子串为例
记忆化搜索 记忆化搜索是一种优化递归算法的方法,通过将已经计算过的子问题的结果存储起来(通常使用哈希表或数组),避免重复计算相同的子问题。 本质上是通过缓存中间结果来减少计算的重复性。 动态规划 动态规划是通过将问题分…...
Tree Compass( Codeforces Round 934 (Div. 2) )
Tree Compass( Codeforces Round 934 (Div. 2) ) You are given a tree with n n n vertices numbered 1 , 2 , … , n 1, 2, \ldots, n 1,2,…,n. Initially, all vertices are colored white. You can perform the following two-step operation: …...
【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】2.17 掩码数组:缺失值处理的优雅方案
2.17 掩码数组:缺失值处理的优雅方案 目录 #mermaid-svg-12vjJJbyudPnkYBO {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-12vjJJbyudPnkYBO .error-icon{fill:#552222;}#mermaid-svg-12vjJJbyudPnkYBO…...
PHP 常用函数2025.02
PHP implode() 函数 语法 implode(separator,array) 参数描述separator可选。规定数组元素之间放置的内容。默认是 ""(空字符串)。array必需。要组合为字符串的数组。 技术细节 返回值:返回一个由数组元素组合成的字符串。PHP 版…...
react中如何获取dom元素
实现代码 const inputRef useRef(null) inputRef.current.focus()...
【C++】继承(下)
大家好,我是苏貝,本篇博客带大家了解C的继承(下),如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 目录 5.继承与友元6.继承与静态成员7.复杂的菱形继承及菱形虚拟继承8.继…...
C语言实现字符串排序:从代码到原理深度解析
在编程的世界里,字符串处理是一项基础且重要的技能。今天,我们通过分析一段C语言代码来深入了解如何对字符串进行排序。 一、代码呈现 #include <stdio.h> #include <string.h> int main() { char s[1001]; scanf("%s", s); int…...
Vue3的el-table-column下拉输入实时查询API数据选择的实现方法
由于本人对el-table-column有下拉输入选择的要求,根据网上搜索的资料及本人优化,推出我比较满意的方法,供各位读者参考使用。 效果图 el-table-column写法 <el-table-columnlabel"货品编号"align"center"prop"…...
【数据结构】_链表经典算法OJ:复杂链表的复制
目录 1. 题目链接及描述 2. 解题思路 3. 程序 1. 题目链接及描述 题目链接:138. 随机链表的复制 - 力扣(LeetCode) 题目描述: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,…...
Vue 图片引用方式详解:静态资源与动态路径访问
目录 前言1. 引用 public/ 目录2. assets/ 目录3. 远程服务器4. Vue Router 动态访问5. 总结6. 扩展(图片不显示) 前言 🤟 找工作,来万码优才:👉 #小程序://万码优才/r6rqmzDaXpYkJZF 在 Vue 开发中&#x…...
chatGPT写的网页版贪吃蛇小游戏
chatGPT写的网页版贪吃蛇小游戏 前言网页版贪吃蛇小游戏 前言 之前无聊,让ChatGPT写了一段基于html语言的贪吃蛇小游戏代码 网页版贪吃蛇小游戏 将以下内容复制到记事本,重命名为xxx.html即可打开浏览器游玩 这里是一个使用HTML、CSS和JavaScript编写…...
Python量化交易助手:xtquant的安装与应用
Python量化交易助手:xtquant的安装与应用 技术背景和应用场景 在量化交易领域,Python因其强大的库支持和灵活性成为了许多开发者的首选语言。其中,xtquant 是迅投官方开发的一个Python包,专门用于与miniqmt通信,实现…...
前缀和算法
文章目录 算法总览题目1371.每个元音包含偶数次的最长子字符串 算法总览 题目 1371.每个元音包含偶数次的最长子字符串 1371.每个元音包含偶数次的最长子字符串 参考博主的讲解 思路分析:就是得使用前缀和记录情况,dp[i][j]表示s[0] 到s[i] 中&…...
Qt常用控件 输入类控件
文章目录 1.QLineEdit1.1 常用属性1.2 常用信号1.3 例子1,录入用户信息1.4 例子2,正则验证手机号1.5 例子3,验证输入的密码1.6 例子4,显示密码 2. QTextEdit2.1 常用属性2.2 常用信号2.3 例子1,获取输入框的内容2.4 例…...
《最小阻力之路》关于愿景的理解和思考
一、愿景的形成机制 1. 愿景的三层来源 来源层级形成机制案例潜在偏差风险① 本能冲动层对快感/痛苦的即时反应"想暴富"源于缺钱焦虑易被短期情绪劫持② 社会镜像层内化外界标准(家庭/社会/文化)"必须考研"因家人期待混淆他人需求…...
Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群
Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群 简介Kubernetes 的工作流程概述Kubernetes v1.29.13 版本Ubuntu 22.04 系统安装部署 Kubernetes v1.29.13 集群 1 环境准备1.1 集群IP规划1.2 初始化步骤(各个节点都需执行)1.2.1 主机名与IP地址解析1.…...
虚幻基础17:动画层接口
能帮到你的话,就给个赞吧 😘 文章目录 animation layer interface animation layer interface 动画层接口:动画图表的集。仅有名字。 添加到动画蓝图中,由动画蓝图实现动画图表。...
无人机PX4飞控 | PX4源码添加自定义uORB消息并保存到日志
PX4源码添加自定义uORB消息并保存到日志 0 前言 PX4的内部通信机制主要依赖于uORB(Micro Object Request Broker),这是一种跨进程的通信机制,一种轻量级的中间件,用于在PX4飞控系统的各个模块之间进行高效的数据交换…...
HTMLCSS :下雪了
这段代码创建了一个动态的雪花飘落加载动画,通过 CSS 技术实现了雪花的下落和消失效果,为页面添加了视觉吸引力和动态感。 大家复制代码时,可能会因格式转换出现错乱,导致样式失效。建议先少量复制代码进行测试,若未能…...
如何处理 Typecho Joe 主题被抄袭或盗版的问题
在开源社区中,版权保护是一个非常重要的话题。如果你发现自己的主题(如 Joe 主题)被其他主题(如子比主题)抄袭或盗版,你可以采取以下措施来维护自己的权益。 一、确认侵权行为 在采取任何行动之前…...
从iRMB到EMO:构建下一代轻量级密集预测模型的统一架构解析
1. 从iRMB到EMO:轻量级密集预测模型的进化之路 当我们在手机上使用人脸解锁功能,或是用修图软件一键抠图时,背后都离不开密集预测模型的支撑。这类模型需要处理图像中每个像素点的信息,传统方案要么计算量太大,要么精度…...
用Python脚本让Crazyflie 2.X无人机动起来:手把手教你写第一个自主飞行程序
用Python脚本让Crazyflie 2.X无人机动起来:从零编写自主飞行程序 当第一次看到Crazyflie这个巴掌大的无人机在桌面上悬停时,我意识到微小型飞行器的编程控制远比想象中更有趣。与传统无人机不同,Crazyflie 2.X系列通过Python脚本就能实现毫米…...
跨平台文件同步方案:OpenClaw+Qwen3-32B智能归档系统
跨平台文件同步方案:OpenClawQwen3-32B智能归档系统 1. 为什么需要智能文件同步 作为一个长期在多台设备间切换工作的开发者,我深受文件管理混乱的困扰。Mac上的设计稿、Windows里的开发文档、Linux服务器上的日志文件——这些散落在各处的数据就像一座…...
LaTeX表格缩放实战:从手动微调到智能适配
1. LaTeX表格缩放的核心挑战 写论文时最头疼的莫过于遇到超宽表格——明明数据很清晰,一放到LaTeX里就溢出页面边界,要么被拦腰截断,要么挤得文字重叠。我审过上百篇学术论文,发现90%的表格排版问题都源于没有掌握正确的缩放技巧。…...
MiddleBury与SceneFlow数据集相机参数解析与深度图生成实战
1. MiddleBury与SceneFlow数据集简介 MiddleBury和SceneFlow是计算机视觉领域两个非常重要的立体视觉数据集。MiddleBury数据集由Middlebury College发布,包含了大量高质量的立体图像对,这些图像对由两台相机在同一时间、不同位置拍摄,涵盖了…...
MacBook安装OpenClaw实录:M1芯片适配Qwen3-32B镜像的解决方案
MacBook安装OpenClaw实录:M1芯片适配Qwen3-32B镜像的解决方案 1. 为什么要在M1 MacBook上折腾OpenClaw? 作为一个长期使用MacBook Pro(M1芯片)的技术爱好者,我一直在寻找能够充分利用本地计算资源的AI工具。当我第一…...
经典游戏现代化:让魔兽争霸III重获新生的适配工具
经典游戏现代化:让魔兽争霸III重获新生的适配工具 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 当你在4K显示器上启动魔兽争霸III时&…...
如何让Windows 11重获新生?系统优化工具Win11Debloat全面评测
如何让Windows 11重获新生?系统优化工具Win11Debloat全面评测 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本,用于从Windows中移除预装的无用软件,禁用遥测,从Windows搜索中移除Bing,以及执行各种其他更改以…...
微信小程序onLaunch异步问题实战:如何确保Page的onLoad在onLaunch完成后执行?
微信小程序异步初始化难题:5种方案确保onLaunch与onLoad的执行顺序 微信小程序的启动流程看似简单,却隐藏着一个让不少开发者踩坑的异步陷阱。当你在app.js的onLaunch中进行网络请求或异步操作时,页面层级的onLoad可能已经迫不及待地开始执行…...
WorkshopDL:轻量级跨平台资源获取工具的技术解析与实战指南
WorkshopDL:轻量级跨平台资源获取工具的技术解析与实战指南 【免费下载链接】WorkshopDL WorkshopDL - The Best Steam Workshop Downloader 项目地址: https://gitcode.com/gh_mirrors/wo/WorkshopDL 在数字内容创作与游戏模组管理领域,高效获取…...
