一、学前花絮
我们之前对算法的学习包括基础知识如数据结构及大致常用算法类型。又学习了贪心算法、回溯算法、分治算法、枚举算法、递归算法并结合实际情况进行示例。今天学习动态规划算法思想，简答说这一算法就是：用"记住过去"解决复杂问题。
二、Python实现动态规划算法
2.1 动态规划的核心思想
动态规划（Dynamic Programming，DP）不是"动态地编程"，而是"聪明地记住结果，避免重复计算"。
最简单的比喻
想象你要爬10级台阶，每次可以爬1级或2级。 问：有多少种不同的爬法？ 如果你从第1级开始想，会想疯掉。 但如果你从最后一级倒着推，就简单了。 这就是动态规划思维。 |
2.2 从斐波那契数列理解动态规划
问题：计算第n个斐波那契数
斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, ...
公式：F(n) = F(n-1) + F(n-2)，其中F(0)=0, F(1)=1
方法1：朴素递归（❌ 低效）
输出结果：
我们计算一下fib_naive(40)花费多少时间：
输出结果：
从以上结果看出，计算fib(40)花费了64秒多，超过1分钟！
为什么这么慢，因为出现了问题：大量重复计算！
方法2：动态规划（✅ 高效）
输出结果：
以上结果瞬间得到，同样我们计算一下fib(40)花费的时间：
输出结果：
从以上结果看出，同样计算fib序列，动态规划要比朴素递归方法快10,063,664(约1千万)倍！这就是算法的魅力，我们编写程序的时候，第一步是在完成功能，而之后呢，要花费很多时间在优化程序上。优化的工作包括代码的封装、注释，也包括代码效率。而让代码高效最重要的方法就是用到合适的算法。
对于动态规划比较朴素递归方法的改进：把中间结果存起来，避免重复计算。
2.3 动态规划的正式定义
三大特征
与分治法的区别：
2.4 动态规划的核心步骤
四步解题法
2.5 经典问题1：爬楼梯
问题描述：有n阶楼梯，每次可以爬1阶或2阶
问：有多少种不同的方法爬到楼顶？
动态规划解法：
输出结果：
空间优化版：
经典问题2：背包问题
之前我们用贪心法处理过背包问题，现在用动态规划算法：
0-1背包问题
动态规划解法：
调用程序进行测试：
输出结果：
2.7 动态规划的适用场景
识别DP问题的特征
典型DP问题分类
2.8 学习建议
2.9 以上内容的总结
动态规划的本质：用空间换时间，记住中间结果，避免重复计算。
核心要点
l不是算法，是思想：一种解决问题的方法论
l核心是状态定义：好的状态定义是成功的一半
l关键是递推关系：找到如何从已知推到未知
l基础是初始条件：最简单的子问题的解
适用场景
l求最优解（最大、最小）
l计数问题（多少种方法）
l存在性问题（是否可能）
l子问题重叠且相关
一句话总结
动态规划 = 分治思想 + 记忆化存储 + 递推求解
当你面对一个复杂问题时，先问自己：
l能分解为子问题吗？
l子问题会重复计算吗？
l能记住子问题的解吗？
如果答案是"是"，那么动态规划可能就是你的解决方案。
三、小结
今天的文章是学习了动态规划算法思想，我们连续多篇文章专门讨论了各种实际工程中常见的算法包括分治、贪心、回溯、枚举、递归，加上今天的动态规划一共6种算法。但算法远远不止这些，我们先从这些常见算法入手，感受一下让代码变得更高效是多么有趣。
让我们保持学习的热情，2026年一马当先！
