1. 动态规划入门三部曲：从斐波那契到爬楼梯问题
最近在代码随想录算法训练营第三十八天的内容中，我们遇到了三个经典的动态规划入门题目：509.斐波那契数、70.爬楼梯和746.使用最小花费爬楼梯。这三个题目看似简单，却完美诠释了动态规划的核心思想。作为算法学习路上的必经关卡，它们值得每个程序员深入理解。
我在最初学习动态规划时，也曾被各种复杂的状态转移方程吓到，直到遇到这三个"友好"的题目才恍然大悟。今天，我就从实际编码的角度，带大家拆解这三个问题的解法，分享一些只有踩过坑才能获得的经验。无论你是刚开始刷题的新手，还是想巩固基础的进阶者，这篇文章都能给你带来直接可用的解题思路和优化技巧。
2. 斐波那契数：动态规划的Hello World
2.1 问题描述与递归解法
斐波那契数列是理解递归和动态规划最经典的例子。题目要求我们实现一个函数，计算第n个斐波那契数。斐波那契数列的定义非常简单：F(0) = 0，F(1) = 1，对于n > 1的情况，F(n) = F(n-1) + F(n-2)。
最直观的解法就是递归：
def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)这个解法虽然简洁，但存在严重的性能问题。我曾在本地测试计算fib(40)，结果等了近10秒才出结果。原因在于递归树中存在大量重复计算，时间复杂度达到了惊人的O(2^n)。
提示：在面试中，如果直接给出这种递归解法而不指出问题，可能会给面试官留下对算法复杂度不敏感的负面印象。
2.2 记忆化搜索优化
解决重复计算最直接的方法就是加入缓存，也就是记忆化搜索(Memoization)技术：
def fib(n, memo={}): if n <= 1: return n if n not in memo: memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n]这个优化将时间复杂度降到了O(n)，因为每个子问题只需要计算一次。空间复杂度也是O(n)，因为需要存储所有中间结果。我在实际测试中发现，计算fib(40)的时间从10秒降到了几乎可以忽略不计的程度。
2.3 动态规划解法
记忆化搜索是自顶向下的解法，而动态规划通常是自底向上的。我们可以使用一个数组来存储中间结果：
def fib(n): if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]这种解法的时空复杂度都是O(n)。但在实际应用中，我们还可以进一步优化空间复杂度。
2.4 空间优化技巧
观察状态转移方程，我们发现当前状态只依赖于前两个状态，因此不需要存储整个数组：
def fib(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b这个版本的空间复杂度降到了O(1)，是面试中最推荐的写法。我在刷题时发现，很多动态规划问题都可以用类似的滚动数组技巧优化空间。
3. 爬楼梯问题：斐波那契的变种
3.1 问题描述与建模
爬楼梯问题是这样的：假设你正在爬楼梯，每次可以爬1或2个台阶。问有多少种不同的方法可以爬到第n阶。
我第一次看到这个问题时，并没有立刻意识到它和斐波那契数的联系。直到画出几阶楼梯的可能情况后才发现规律：
- 到第1阶：1种方法(1)
- 到第2阶：2种方法(1+1, 2)
- 到第3阶：3种方法(1+1+1, 1+2, 2+1)
- 到第4阶：5种方法...
这明显就是斐波那契数列！状态转移方程为：dp[n] = dp[n-1] + dp[n-2]
3.2 标准动态规划解法
基于这个发现，我们可以写出和斐波那契数几乎相同的代码：
def climbStairs(n): if n <= 2: return n dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]同样，我们也可以应用空间优化：
def climbStairs(n): if n <= 2: return n a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b3.3 扩展思考：如果步长变化怎么办？
在实际面试中，问题可能会变化。比如，如果每次可以爬1、2或3个台阶，解法会怎样变化？这时状态转移方程就变成了： dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
这个变种考察的是能否灵活应用动态规划思想，而不是死记硬背。我在面试辅导中发现，很多同学能解原题但遇到变种就束手无策，原因在于没有真正理解动态规划的本质。
4. 最小花费爬楼梯：动态规划的实用案例
4.1 问题描述与状态定义
746题是这样的：给定一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦支付此费用，可以选择向上爬一个或两个台阶。可以从下标为0或1的台阶开始爬楼梯，求达到楼梯顶部的最小花费。
这个问题比前两个更贴近实际应用场景。关键在于正确定义状态。经过几次尝试，我发现可以定义dp[i]为到达第i阶时的最小总花费。
4.2 状态转移方程推导
根据题意，到达第i阶有两种方式：
- 从i-1阶花费cost[i-1]上来
- 从i-2阶花费cost[i-2]上来
因此，状态转移方程为： dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
初始条件是dp[0] = dp[1] = 0，因为我们可以选择从这两阶开始而不需要任何花费。
4.3 完整实现代码
基于以上分析，我们可以写出如下代码：
def minCostClimbingStairs(cost): n = len(cost) dp = [0] * (n + 1) for i in range(2, n + 1): dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) return dp[n]同样，这个解法也可以进行空间优化：
def minCostClimbingStairs(cost): a = b = 0 for i in range(2, len(cost) + 1): a, b = b, min(a + cost[i-2], b + cost[i-1]) return b4.4 常见错误与调试技巧
在解决这个问题时，我最初犯过几个典型错误：
- 错误地将dp[i]定义为从第i阶开始的最小花费，导致状态转移混乱
- 忽略了可以从0或1阶开始的条件，初始条件设置错误
- 数组长度处理不当，忘记结果是dp[n]而不是dp[n-1]
调试这类问题时，我建议：
- 先手动计算小例子（如cost=[10,15,20]）
- 打印出整个dp数组检查是否符合预期
- 特别注意数组边界条件
5. 动态规划解题的通用方法论
通过这三个题目，我们可以总结出解决动态规划问题的通用步骤：
- 确定dp数组及其下标的含义
- 推导状态转移方程
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组（用于验证）
在实际刷题中，我发现很多同学卡在第1步和第2步。我的经验是：
- 先尝试暴力递归解法，观察是否存在重叠子问题
- 画图帮助理解问题，特别是对于二维dp问题
- 从小规模例子入手，寻找规律
- 不要急于写代码，先确保状态定义正确
6. 性能对比与进阶思考
为了更直观地理解不同解法的性能差异，我做了如下测试（计算fib(40)）：
| 方法 | 时间复杂度 | 空间复杂度 | 实际运行时间 |
|---|---|---|---|
| 朴素递归 | O(2^n) | O(n) | ~10秒 |
| 记忆化搜索 | O(n) | O(n) | <1毫秒 |
| 标准DP | O(n) | O(n) | <1毫秒 |
| 优化DP | O(n) | O(1) | <1毫秒 |
对于更复杂的问题，动态规划的优势会更加明显。比如背包问题、最长公共子序列等，暴力解法完全不可行，而动态规划能在合理时间内解决。
7. 常见问题与解决方案
在指导他人学习动态规划时，我收集了一些常见困惑和解决方法：
Q: 如何判断一个问题是否能用动态规划解决？ A: 通常具有"最优子结构"和"重叠子问题"特性的问题适合DP。可以先尝试分治法，如果发现重复计算，就考虑DP。
Q: 状态转移方程总是想不出来怎么办？ A: 尝试先列举小规模例子，寻找规律。也可以先写出暴力递归，再观察如何优化。
Q: 边界条件经常出错怎么办？ A: 特别关注dp数组的初始化和索引范围。建议先明确dp[i]的定义，再处理边界。
Q: 如何从二维DP降维到一维？ A: 观察状态转移是否只依赖于有限的几个状态。如果是，可以用滚动数组优化。
8. 实战练习建议
为了真正掌握动态规划，我建议的练习路径是：
- 先熟练掌握这三个基础题目
- 尝试类似难度的题目（如198.打家劫舍）
- 逐步过渡到更复杂的问题（如背包问题）
- 最后挑战hard级别的DP问题
在代码随想录的算法训练营中，题目顺序就是这样精心设计的。我自己的经验是，每个DP问题至少做两遍：第一遍理解思路，第二遍独立实现并优化。
