悯拄等 发表于 2025-7-14 23:16:06

动态规划

动态规划

背景：

从递归到记忆化搜索再到动态规划：

递归思路：


方法论


[*]方法一：循序渐进
通过引入动态规划的逻辑，来解决动态规划的问题：首先从递归出发，写出递归表达式，根据递归表达式，得到记忆化搜索，再有记忆化搜索翻译为递归（去掉递归中的递的过程）（结合198.打家劫舍来理解）：

[*]dfs(i,j) => dp数组
[*]递归 => 循环
[*]根据递归边界初始化数组

[*]方法二：五部曲


[*]dp数组以及下标含义
[*]递推公式
[*]遍历顺序：前后顺序，内外顺序
[*]数组初始化，结合前三者
[*]打印dp数组：验证，找错
动态规划模型


[*]0-1背包


[*]完全背包

小结：0-1背包与完全背包模型是对递归中枚举该元素选或者不选两种选择对最终目标造成的影响的总结，两者的区别在于01背包中的物品只能选一次，而完全背包的物品的选择则没有次数限制
总结

记忆化搜索即在递归过程中，缓存递归返回的结果，每次进入递归之前判断该结果是否已经计算过了。而在递归过程中，通常是在归的过程计算答案，放入缓存。由此，省去递的过程，直接从头循环开始推到，得到归的最终结果，这个就是动态规划的思想。通常递归的与动态规划的时间复杂度是相同的，因为他们都是搜索，而动态规划是自底向上的，递归通常是自顶向下的。在空间复杂度上，动态规划通常可以做到优于递归，因为递归需要隐式的记录返回位置，而动态规划的状态转移方程往往只涉及有限的数组。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

盗衍 发表于 2025-12-25 00:25:12

鼓励转贴优秀软件安全工具和文档！

炀餮氢 发表于 2025-12-31 09:37:44

很好很强大我过来先占个楼 待编辑

啪炽 发表于 2026-1-13 01:25:04

新版吗？好像是停更了吧。

簑威龙 发表于 2026-1-16 10:34:59

新版吗？好像是停更了吧。

劳暄美 发表于 2026-1-19 12:16:47

热心回复！

汤流婉 发表于 2026-1-23 08:20:57

东西不错很实用谢谢分享

秦晓曼 发表于 2026-1-25 06:48:23

感谢发布原创作品，程序园因你更精彩

祖娅曦 发表于 2026-1-25 09:31:15

感谢分享，下载保存了，貌似很强大

疝镜泛 发表于 2026-1-28 10:19:50

谢谢楼主提供！

告陕无 发表于 2026-2-1 20:15:14

喜欢鼓捣这些软件，现在用得少，谢谢分享！

梁宁 发表于 2026-2-3 07:11:54

这个好，看起来很实用

肿抢 发表于 2026-2-8 01:26:45

分享、互助 让互联网精神温暖你我

晁红叶 发表于 2026-2-8 22:07:47

感谢，下载保存了

袁曼妮 发表于 2026-2-9 14:02:08

感谢，下载保存了

臧莞然 发表于 2026-2-9 17:21:31

很好很强大我过来先占个楼 待编辑

判涔 发表于 2026-2-9 22:14:48

不错，里面软件多更新就更好了

缑娅瑛 发表于 2026-2-10 06:20:00

感谢，下载保存了

度阡舅 发表于 2026-2-10 08:33:31

感谢分享，学习下。

宗和玉 发表于 2026-2-10 15:43:51

前排留名，哈哈哈
页: [1] 2
查看完整版本: 动态规划