动态规划是一种解决复杂问题的艺术，它将大问题拆解为小问题，通过保存子问题的解来避免重复计算，最终实现高效求解。本文将带你深入理解动态规划的核心理念和实践技巧。
一、什么是动态规划？
动态规划（Dynamic Programming，简称DP）是一种解决多阶段决策过程最优化问题的方法。其核心思想是：如果一个大问题的最优解包含其子问题的最优解，则称该问题具有最优子结构性质。
1.1 动态规划与贪心算法的区别
| 特性 | 动态规划 | 贪心算法 |
|---|---|---|
| 状态推导 | 当前状态由前一个状态推导 | 局部直接选最优，无状态推导 |
| 求解方式 | 自底向上或自顶向下 | 自顶向下，一步到位 |
| 适用场景 | 有重叠子问题的最优化 | 问题具有贪心选择性质 |
| 全局最优 | 保证得到全局最优解 | 不一定得到全局最优解 |
示例说明：对于背包问题，动态规划中dp[j]是由dp[j-weight[i]]推导出来的，通过比较不同选择得到最优解；而贪心算法每次只选择当前价值最大的物品，不考虑全局最优。
1.2 动态规划的三要素
- 重叠子问题：问题可以被分解为多个重叠的子问题
- 最优子结构：问题的最优解包含其子问题的最优解
- 状态转移方程：描述状态之间如何转移的数学表达式
二、动态规划的解题框架
解决动态规划问题可以遵循一个标准化的五步曲，这是掌握DP的关键：
2.1 动态规划五步曲
第一步：确定dp数组及其下标的含义
- dp数组是什么？一维、二维还是多维？
- 每个下标代表什么状态？
第二步：确定递推公式（状态转移方程）
- 如何从已知状态推导出未知状态？
- 这是动态规划的核心，也是最难的部分
第三步：dp数组的初始化
- 基础情况（base case）是什么？
- 哪些状态可以直接确定而不需要推导？
第四步：确定遍历顺序
- 应该从前往后遍历还是从后往前？
- 多维dp中，先遍历哪个维度？
第五步：举例推导dp数组
- 用具体例子验证递推公式和遍历顺序
- 这是调试和验证思路的关键步骤
2.2 两种实现方式对比
| 实现方式 | 特点 | 适用场景 | 代码框架示例 |
|---|---|---|---|
| 自顶向下（带备忘录递归） | 从原问题出发，递归分解，记忆化存储结果 | 问题自然适合递归表达，子问题重叠明显 | python<br>def dp(状态):<br> if 状态 in memo:<br> return memo[状态]<br> res = 计算(状态)<br> memo[状态] = res<br> return res<br> |
| 自底向上（迭代递推） | 从基础情况开始，逐步构建到原问题 | 问题有明显的递推关系，适合循环实现 | python<br>dp[0] = base_case<br>for i in range(1, n+1):<br> dp[i] = 转移方程(dp[...])<br>return dp[n]<br> |
三、经典问题解析
3.1 斐波那契数列问题
问题描述：计算第n个斐波那契数，其中F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。
暴力递归解法（时间复杂度O(2^n)）：
deffib(n):ifn<=1:returnnreturnfib(n-1)+fib(n-2)问题：存在大量重复计算，如fib(5)会重复计算fib(3)两次。
带备忘录的递归解法（时间复杂度O(n)）：
deffib_memo(n,memo={}):ifn<=1:returnnifninmemo:returnmemo[n]memo[n]=fib_memo(n-1,memo)
)
)