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

动态规划与记忆化搜索的区别与联系

news 来源：原创 2025/8/21 3:54:53

记忆化搜索（Memoization）和动态规划（Dynamic Programming, DP）都是解决重叠子问题的高效算法技术，但它们有着不同的实现方式和特点。

1. 基本概念

记忆化搜索（自顶向下）

本质：带有缓存机制的递归
方向：从原问题出发，分解为子问题（Top-down）
特点：
- 递归实现
- 只计算必要的子问题
- 通过缓存避免重复计算

动态规划（自底向上）

本质：迭代式的填表法
方向：从基础子问题开始，逐步构建最终解（Bottom-up）
特点：
- 迭代实现
- 通常计算所有可能的子问题
- 通过表格系统性地存储中间结果

2. 核心区别

特性	记忆化搜索	动态规划
实现方式	递归	迭代
计算顺序	自顶向下（从目标问题开始分解）	自底向上（从基础情况开始构建）
子问题计算	按需计算（懒计算）	全部计算
空间复杂度	通常较高（递归栈+记忆表）	通常可优化
代码可读性	更直观（接近问题描述）	需要明确状态转移顺序
适用场景	子问题不明确或稀疏	子问题明确且密集

3. 具体对比

计算过程示例（以斐波那契数列为例）

记忆化搜索：

python

memo = {0:0, 1:1}def fib(n):if n not in memo:memo[n] = fib(n-1) + fib(n-2)return memo[n]

→ 计算路径：fib(5)→fib(4)→fib(3)→fib(2)→fib(1)/fib(0)

动态规划：

python

def fib(n):dp = [0,1] + [0]*(n-1)for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

→ 计算顺序：dp[0], dp[1], dp[2], ..., dp[n]

性能特点

记忆化搜索可能：
- 存在递归开销（栈空间、函数调用成本）
- 对于某些问题可能跳过不必要的子问题计算
- 更容易实现（特别是复杂的状态转移）
动态规划通常：
- 运行效率更高（无递归开销）
- 更容易进行空间优化（如滚动数组）
- 需要更明确的状态转移顺序

4. 如何选择

优先使用记忆化搜索当：

问题状态空间复杂或不规则
只有部分子问题需要被计算
递归关系直观但迭代顺序不明显
原型开发阶段（更易编写和调试）

优先使用动态规划当：

需要最优的空间复杂度
子问题有明确的计算顺序
需要极致的运行时性能
问题状态空间规整且密集

5. 经典问题对比

打家劫舍问题实现

记忆化搜索实现：

int dfs(int i, int* nums, int* memo) {if (i < 0) return 0;if (memo[i] != -1) return memo[i];int not_rob = dfs(i-1, nums, memo);int rob = dfs(i-2, nums, memo) + nums[i];return memo[i] = max(not_rob, rob);
}

动态规划实现：

int rob(int* nums, int n) {if (n == 0) return 0;int dp[n+1];dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= n; i++) {dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);}return dp[n];
}

6. 相互转换

两者本质上是等价的，可以相互转换：

记忆化搜索 → DP：将递归改为迭代，明确计算顺序
DP → 记忆化搜索：将递推关系改写为递归，添加缓存

在实际应用中，许多问题先用记忆化搜索设计解法，再转换为DP进行优化是常见的解题路径。

动态规划与记忆化搜索的区别与联系

记忆化搜索（Memoization）和动态规划（Dynamic Programming, DP）都是解决重叠子问题的高效算法技术，但它们有着不同的实现方式和特点。 1. 基本概念记忆化搜索（自顶向下） 本质：带有…...

编程日记 2025/8/21 3:54:53

html+js+clickhouse环境搭建

实验背景： 我目前有一台服务器A，和一台主机B，两台设备属于同一局域网，相互之间可以通讯。服务器A中部署着clickhouse，我在主机B中想直接通过javascript代码访问服务器中的clickhouse数据库并获取数据。 ClickHouse 服务…...

编程日记 2025/8/21 3:45:48

生命护航行动再启航！

温州好人陈飞携防溺水课堂，为乡村少年宫筑起安全防线图文作者：华夏之音/李望随着夏日热浪的滚滚而来，楠溪江畔的安全警钟再次响起。在这片如诗如画的土地上，一场旨在保护青少年生命安全的防溺水课堂活动拉开了…...

编程日记 2025/8/21 3:49:11

Android Compose Activity 页面跳转动画详解

下面我将全面详细地介绍在 Compose 中实现 Activity 跳转动画的各种方法，包括基础实现、高级技巧和最佳实践。一、基础 Activity 过渡动画 1. overridePendingTransition 传统方式这是最基础且兼容性最好的方法，适用于所有 Android 版本。实现步骤…...

编程日记 2025/8/21 3:53:09

Android启动初始化init.rc详解

1. Android启动与init.rc简介 1.1 Android启动过程一张图简单阐述一下 （网络图片，侵删） 1.2 init.rc 简介 Linux的重要特征之一就是一切都是以文件的形式存在的，例如，一个设备通常与一个或多个设备文件对应。这些…...

编程日记 2025/8/21 3:51:27

Linux驱动开发-①regmap②IIO子系统

Linux驱动开发-IIO驱动一，regmap二，IIO子系统2.1初始化相关工作2.2 通道2.3 读实现 over 一，regmap 对于spi和i2c,读写寄存器的框架不同，但设备本质一样，因此就有了regmap模型来对其进行简化，提供统一的接…...

编程日记 2025/8/21 3:47:31

HTML5好看的水果蔬菜在线商城网站源码系列模板5

文章目录 1.设计来源1.1 主界面1.2 关于我们1.3 商品服务1.4 果蔬展示1.5 联系我们1.6 商品具体信息1.7 登录注册 2.效果和源码2.1 动态效果2.2 源代码源码下载万套模板，程序开发，在线开发，在线沟通作者：xcLeigh 文章地址&#…...

编程日记 2025/8/21 3:40:34

L2-033 简单计算器满分笔记

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。如上图所示，计算器由两个堆栈组成，一个堆栈 S1 存放数字，另一个堆栈 S2 存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就…...

编程日记 2025/8/17 18:20:52

其他网页正常进入，但是CSDN进入之后排版混乱

显示不正常，排版混乱解决方法： ①打开网络设置 ②更改适配器 ③所连接的网络 --右键属性然后就可以正常访问了。...

编程日记 2025/8/17 20:09:34

BFC详解

1.定义： FC的全称为Formatting Conttext,元素在标准流里面块级元素的布局属于Block Formatting Context(BFC)——即block level box都是BFC中布局行内级元素的布局属于Inline Formatting Context (IFC) 2.那么在哪些情况下会创建BFC？ 根元素…...

编程日记 2025/8/19 17:53:34

1.实验拓扑 2.实验配置 [S1]dis cu #version 7.1.070, Alpha 7170 #sysname S1 # vlan 10 # vlan 20 # interface GigabitEthernet1/0/1port link-mode bridgeport link-type trunkport trunk permit vlan 1 10 20combo enable fiber # interface GigabitEthernet1/0/2port li…...

编程日记 2025/8/20 19:27:31

idea mvn执行打包命令后控制台乱码

首先在idea中查看maven的编码方式执行mvn -v命令查看编码语言是GBK C:\Users\13488>mvn -v Apache Maven 3.6.3 (cecedd343002696d0abb50b32b541b8a6ba2883f) Maven home: D:\maven\apache-maven-3.6.3\bin\.. Java version: 1.8.0_202, vendor: Oracle Corporation, runt…...

编程日记 2025/8/19 23:06:46

JSON.parse(JSON.stringify()) 与 lodash 的 cloneDeep：深度拷贝的比较与基础知识

JSON.parse(JSON.stringify()) 与 lodash 的 cloneDeep：深度拷贝的比较与基础知识在 JavaScript 开发中，**深拷贝（Deep Copy）**是一个常见需求，尤其是在处理复杂对象和嵌套数据结构时。JSON.parse(JSON.stringify(o…...

编程日记 2025/8/17 21:27:29

搭建用友U9Cloud ERP及UAP IDE环境

应用环境 Microsoft Windows 10.0.19045.5487 x64 专业工作站版 22H2Internet Information Services - 10.0.19041.4522Microsoft SQL Server 2019 - 15.0.2130.3 (X64)Microsoft SQL Server Reporing Services 2019 - 15.0.9218.715SQL Server Management Studio -18.6 laster…...

编程日记 2025/8/20 5:56:58

Linux 系统新磁盘分区XFS挂载

以下是Linux系统中对新硬盘进行XFS文件系统格式化和挂载的完整操作指南： 一、确认硬盘识别 ‌查看已识别硬盘‌ 执行 lsblk 或 fdisk -l 命令，确认新硬盘设备标识（如 /dev/sdb）‌。二、硬盘分区（可选） …...

编程日记 2025/8/20 22:30:36

Oracle测试题目及笔记（单选）

所有题目来自于互联网搜索当 Oracle 服务器启动时，下列哪种文件不是必须的（D）。 A．数据文件 B．控制文件 C．日志文件 D．归档日志文件数据文件、日志文件-在数据库的打开阶段使用控制文件-在数…...

编程日记 2025/8/17 18:20:57

C语言链接数据库

目录使用 yum 配置 mysqld 环境查看 mysqld 服务的版本创建 mysql 句柄链接数据库使用数据库增加数据修改数据查询数据获取查询结果的行数获取查询结果的列数获取查询结果的列名获取查询结果所有数据断开链接 C语言访问mysql数据库整体源码通过…...

编程日记 2025/8/20 13:05:58

深入浅出 Redis：核心数据结构解析与应用场景Redis 数据结构

引言：Redis 为何如此之快？数据结构是关键 Redis (Remote Dictionary Server) 作为一款高性能的内存键值数据库，凭借其闪电般的速度和丰富的功能，在缓存、消息队列、排行榜等众多场景中得到了广泛应用。除了基于内存存储这一核心优…...

编程日记 2025/8/18 23:15:10

告别昂贵语音合成服务！用GPT-SoVITS生成你的个性化AI语音

文章目录前言1.GPT-SoVITS V2下载2.本地运行GPT-SoVITS V23.简单使用演示4.安装内网穿透工具4.1 创建远程连接公网地址 5. 固定远程访问公网地址前言今天给大家介绍一款AI语音克隆工具——GPT-SoVITS。这款由花儿不哭大佬开发的工具是一款强大的训练声音模型与音频生成工具…...

编程日记 2025/8/20 18:02:32

前沿要塞：Vue组件安全工程的防御体系重构与技术突围

总章数字世界的钢铁长城在某个凌晨3点的红蓝对抗演练中，某电商平台因组件级XSS漏洞导致千万级用户数据泄露。这不是虚构的灾难场景，而是2023年某A轮企业的真实遭遇。当传统安全方案在新型攻击面前节节败退时，我们需要为Vue组件铸造全新的数字…...

编程日记 2025/8/17 18:20:59

吴恩达深度学习复盘(19)XGBoost简介|神经网络与决策树

XGBoost 多年来，机器学习研究人员提出了许多构建决策树的方法，目前最常用的方法是对样本或决策树的实现收费。其中，XGBoost 是一种非常快速且易于使用的开源实现，已成功用于赢得许多机器学习竞赛和商业应用。算法原理基本思想…...

编程日记 2025/8/19 23:51:26

Docker部署禅道21.6开源版本

将数据库相关环境变量分开，增加注释或空格使得命令更易读。如果你的 MySQL 主机、端口等配置没有变化，应该确保这些信息是安全的，并考虑使用 Docker secrets 或环境变量配置来避免直接暴露敏感信息。 docker run -d -it --privilegedtrue …...

编程日记 2025/8/17 19:49:37

《MySQL：MySQL表结构的基本操作》

创建表 CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; field 表示列名 datatype 表示列的类型 character set 字符集，如果没有指定字符集，则以所在数据…...

编程日记 2025/8/17 20:04:56

C++解析操作mat文件方法-基于vs2019

前言工作中需要将C#脚本转为C++,所转脚本主要功能是进行mat数据文件的解析和矩阵运算。 1.C#版本原C#脚本主要是基于 MathNet.Numerics.data.Matlab、MathNet.Numerics.LineAlgebra.Double、 MathNet.Numerics.LineAlgebra 中的MatlabReader、DenseMatrix、Matrix进行mat文…...

编程日记 2025/8/18 0:26:14

OpenCV 模板匹配方法详解

文章目录 1. 什么是模板匹配？2. 模板匹配的原理2.1数学表达 3. OpenCV 实现模板匹配3.1基本步骤 4. 模板匹配的局限性5. 总结 1. 什么是模板匹配？ 模板匹配（Template Matching）是计算机视觉中的一种基础技术，用于在目…...

编程日记 2025/8/17 20:02:26

自已实现一个远程打印方案解决小程序或APP在外面控制本地电脑打印实现

常规通过小程序或APP在外出时控制本地电脑实现打印功能，可以结合远程桌面技术、云打印服务或开发定制化的远程打印解决方案。但这里我们采用自已的实现方案来解决服务器端实现搭建一个后端socket服务，监听来自手机的打印请求。监听到打印任务后向本…...

编程日记 2025/8/20 7:36:23

Oracle_00000

contents 基本使用基本使用 Oracle安装后会自动创建sys和system这两个用户。 sys用户：具有最高权限。具有sysdba角色，有create database的权限。该用户默认密码是：manager system用户：管理员用户，具有sysoper角色。没…...

编程日记 2025/8/18 20:25:42

深入剖析 ORM：原理、优缺点、场景及多语言框架示例

ORM 即对象关系映射（Object Relational Mapping），它是一种编程技术，其作用是在面向对象编程语言里，把对象模型和关系型数据库的数据结构之间创建起映射，这样开发者就能够使用面向对象的方式来操作数据库&am…...

编程日记 2025/8/17 20:40:43

ARINC818协议-持续

一、帧头帧尾 SOF 和 EOF 分别代表视频帧传输的开始与结束，它们在封装过程有多种状态，SOF 分为 SOFi 和 SOFn，EOF 分为 EOFt 和 EOFn。传输系统中的视频信息包括像素数据信息和辅助数据信息，分别存储在有效数据中的对象 0 和对象…...

编程日记 2025/8/20 14:21:55

【uniapp】uni.setClipboardData 方法失效 bug 解决方案

写了一个 copy 方法，但是怎么也没有弹窗复制成功 <text click"toCopy(myInfo.id)">复制 </text> 逐步打印发现 1 正常打印，2 没有打印，说明问题出现在 setClipboardData 方法执行中 toCopy(n) {// console.log(1,ty…...

编程日记 2025/8/17 20:26:31

智能sc一面

智能sc一面-2025/4/17 更多完善：真实面经 Java 的异常分类异常分为两类，一类Error,一类Execption。这两个类都是Throwable的子类，只有继承Throwable 的类才可以被throw或者catch Error: 表示严重的系统问题，通常与代码无关&am…...

编程日记 2025/8/20 18:20:28

SAP HANA使用命令行快速导出导入

楔子今天折腾了接近一下午，就为了使用SAP HANA自带的命令行工具来导出数据备份。 SAP HANA（后续简称Hana）是内存数据库，性能这一方面上还真没怕过谁。由于SAP HANA提供了Hana Studio这个桌面工具来方便运维和DBA使用&#xf…...

编程日记 2025/8/17 19:04:56

Oracle DBMS_SCHEDULER 与 DBMS_JOB 的对比

Oracle DBMS_SCHEDULER 与 DBMS_JOB 的对比一基本概述对比特性DBMS_JOB (旧版)DBMS_SCHEDULER (新版)引入版本Oracle 7 (1992年)Oracle 10g R1 (2003年)当前状态已过时但仍支持推荐使用的标准设计目的基础作业调度企业级作业调度系统二功能特性对比 2.1 作业定义能力 …...

编程日记 2025/8/19 6:38:25

【音视频】音视频FLV合成实战

FFmpeg合成流程示例本程序会⽣成⼀个合成的⾳频和视频流，并将它们编码和封装输出到输出⽂件，输出格式是根据⽂件扩展名⾃动猜测的。示例的流程图如下所示。 ffmpeg 的 Mux 主要分为三步操作： avformat_write_header ： 写⽂件…...

编程日记 2025/8/19 18:30:47

10.（vue3.x+vite）div实现tooltip功能（css实现）

1：效果截图 2：代码实现 <template><div><div class="tooltip" style="margin-top: 20%; margin-left: 20%; background-color: blueviolet; color: white;...

编程日记 2025/8/17 20:49:58

代码随想录算法训练营第三十七天| 52. 携带研究材料 518.零钱兑换II 377. 组合总和 Ⅳ 70. 爬楼梯(进阶版)

[TOC](代码随想录算法训练营第三十七天| 52. 携带研究材料 518.零钱兑换II 377. 组合总和 Ⅳ 70. 爬楼梯(进阶版) ) 入营第三十七天难度：难计划任务完成任务 52. 携带研究材料动态规划五部曲： 1.确定dp数组以及下标含义 dp[i][j]表示从下标[0-i]的…...

编程日记 2025/8/19 7:42:16

数智化招标采购系统分类及功能亮点

数智化招标采购系统是郑州信源公司运用“互联网”、大数据、人工智能、区块链、物联网等新兴技术，结合供应链管理理念，以招标采购为核心，提供交易、管理、数据、服务、监管为一体的高标准采购管理平台，赋能政企用户实现采购业务全…...

编程日记 2025/8/19 20:13:40

CSS appearance 属性：掌握UI元素的原生外观

在现代网页设计中，为了达到一致的用户体验，我们有时需要让HTML元素模仿操作系统的默认控件样式。CSS中的appearance属性提供了一种简便的方式来控制这些元素是否以及如何显示其默认外观。本文将详细介绍appearance属性，并通过实际代码示例来展…...

编程日记 2025/8/19 3:54:42

【JavaScript】二十四、JS的执行机制事件循环 + location + navigator + history

文章目录 1、JS执行机制（事件循环eventloop）2、BOM的window3、location对象3.1 href属性3.2 search属性3.3 hash属性3.4 reload方法 4、navigator对象5、history对象 1、JS执行机制（事件循环eventloop） 以下，两段代码…...

编程日记 2025/8/19 1:21:47

CSS核心笔记002

margin塌陷问题第一个子元素的上margin会作用在父元素上, 最后一个子元素的下margin会作用在父元素上解决 1. 给父元素设置不为0的pandding 2. 给父元素设置宽度不为0 的border 3. 给父元素设置样式 overflow:hiddenmargin合并问题兄弟元素的下外margin和会下面兄弟的上…...

编程日记 2025/8/17 20:13:01

前端路由缓存实现

场景：以一体化为例：目前页面涉及页签和大量菜单路由，用户想要实现页面缓存，即列表页、详情页甚至是编辑弹框页都要实现数据缓存。方案：使用router-view的keep-alive实现。一、实现思路 1.需求梳理需要缓存模块&…...

编程日记 2025/8/17 1:56:19

加密软件的发展：从古典密码到量子安全

在数字化时代，信息安全已成为个人隐私、商业机密乃至国家安全的重要基石。加密软件作为保护信息安全的核心工具，经历了从简单替换到复杂算法的漫长演变过程。本文将系统梳理加密软件的发展历程，分析当前主流技术，并展望未来趋势。…...

编程日记 2025/8/16 23:29:37

用Zotero + Word 宏，一键插入带超链接的参考文献！

第一步：准备好Zotero Word 确认你已经完成以下准备： ✅ 已安装好 Zotero ✅ 已安装好 Zotero Word 插件（一般自动装好了） ✅ Word 可以正常插入参考文献 ✅ 已插入好一组参考文献（可以先插几个测试） …...

编程日记 2025/8/19 13:53:42

Java SpringBoot的自定义配置

一，一个类多个属性的情况 application.properties配置文件写法 my.config.ip127.0.0.1 my.config.port8080自定义配置类：MyTestConfig import org.slf4j.Logger; import org.slf4j.LoggerFactory; import org.springframework.boot.context.properties…...

编程日记 2025/8/20 22:00:09