新闻详情

新闻详情

首页 / 资讯中心 / 详情

动态规划:从递归到最优决策的算法艺术

发布时间:2026/11/20 19:13:54来源:尧图网络
动态规划:从递归到最优决策的算法艺术
动态规划Dynamic Programming简称 DP并非某种具体的算法而是一种将复杂问题分解为简单子问题、并通过存储子问题的解来避免重复计算的算法设计思想。其核心哲学在于用空间换时间解决那些具有最优子结构和重叠子问题特性的难题。不同于贪心算法的局部最优选择动态规划通过穷举所有可能的决策路径确保找到全局最优解。要理解动态规划不妨从最朴素的递归说起。以经典的斐波那契数列为例其数学定义为F(n)F(n−1)F(n−2)F(n) F(n-1) F(n-2)F(n)F(n−1)F(n−2)其中F(0)0,F(1)1F(0)0, F(1)1F(0)0,F(1)1。若直接翻译为递归代码我们会发现计算过程产生了指数级的冗余运算。例如在计算F(5)F(5)F(5)时F(3)F(3)F(3)被重复计算了多次。这种重叠子问题现象导致了巨大的性能浪费。动态规划介入的方式便是引入一个数组dpdpdp来存储已计算的结果这被称为“记忆化搜索”。在正式的文章中我们通常使用“自底向上”的迭代方式来构建 DP。对于斐波那契数列我们定义状态dp[i]dp[i]dp[i]表示第iii个数字的值。状态转移方程为dp[i]dp[i−1]dp[i−2] dp[i] dp[i-1] dp[i-2]dp[i]dp[i−1]dp[i−2]通过初始化dp[0]dp[0]dp[0]和dp[1]dp[1]dp[1]我们可以线性地推导出后续结果。以下是标准的动态规划实现deffibonacci(n:int)-int:ifn1:returnn# 定义 dp 数组dp[0]*(n1)# 初始化边界条件dp[0],dp[1]0,1# 状态转移foriinrange(2,n1):dp[i]dp[i-1]dp[i-2]returndp[n]此代码的时间复杂度为O(n)O(n)O(n)空间复杂度为O(n)O(n)O(n)。进一步观察可以发现dp[i]dp[i]dp[i]仅依赖于前两个状态因此我们可以将空间压缩至O(1)O(1)O(1)deffibonacci_optimized(n:int)-int:ifn1:returnn prev,curr0,1for_inrange(2,n1):prev,currcurr,prevcurrreturncurr动态规划的难点在于状态定义与转移方程的设计。以0-1 背包问题为例这是动态规划中的里程碑式问题。问题描述如下给定nnn个物品每个物品重量为wiw_iwi​价值为viv_ivi​以及一个容量为WWW的背包。求在不超过容量限制的前提下背包能装下的物品最大总价值。我们定义二维状态dp[i][j]dp[i][j]dp[i][j]表示前iii个物品放入容量为jjj的背包中所能获得的最大价值。对于每个物品我们有两种选择放或不放。如果不放则dp[i][j]dp[i−1][j]dp[i][j] dp[i-1][j]dp[i][j]dp[i−1][j]如果放前提是j≥wij \ge w_ij≥wi​则dp[i][j]dp[i−1][j−wi]vidp[i][j] dp[i-1][j-w_i] v_idp[i][j]dp[i−1][j−wi​]vi​。综合二者状态转移方程为dp[i][j]max⁡(dp[i−1][j],dp[i−1][j−wi]vi) dp[i][j] \max(dp[i-1][j], dp[i-1][j-w_i] v_i)dp[i][j]max(dp[i−1][j],dp[i−1][j−wi​]vi​)完整的代码如下defknapsack_01(W,weights,values):nlen(weights)# dp[i][j] 表示前 i 个物品容量为 j 的最大价值dp[[0]*(W1)for_inrange(n1)]foriinrange(1,n1):forjinrange(W1):# 不拿第 i 个物品dp[i][j]dp[i-1][j]# 尝试拿第 i 个物品ifjweights[i-1]:dp[i][j]max(dp[i][j],dp[i-1][j-weights[i-1]]values[i-1])returndp[n][W]同样该问题也可以进行空间优化。由于dp[i]dp[i]dp[i]只依赖于dp[i−1]dp[i-1]dp[i−1]我们可以使用一维数组并从后往前遍历容量jjj以避免数据覆盖。除了背包问题动态规划还广泛应用于字符串处理如最长公共子序列LCS、区间决策如石子合并以及树形结构树形 DP。掌握动态规划的关键在于“勤画表”通过在草稿纸上模拟dpdpdp数组的填充过程往往能直观地发现状态之间的联系。总而言之动态规划不是一蹴而就的技巧而是对问题本质的深度剖析。它要求我们明确“什么是状态”以及“状态如何流转”。当你面对一个问题时若能将其抽象为一个多阶段的决策过程并证明其满足无后效性那么动态规划很可能就是你手中的利刃。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/20 0:44:51

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/19 15:17:14

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/19 20:26:12

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/20 16:11:20

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/20 18:41:01

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/20 0:44:55

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉