动态规划入门：从斐波那契到爬楼梯问题解析

1. 动态规划入门三部曲：从斐波那契到爬楼梯问题

作为一名经历过多次算法面试洗礼的老程序员，我始终认为动态规划（DP）是区分普通开发者和算法高手的分水岭。今天要讨论的这三个题目——斐波那契数、爬楼梯和最小花费爬楼梯，正是动态规划领域最经典的入门"三部曲"。它们看似简单，却蕴含着DP最核心的思想精髓。

记得我最初接触DP时，曾被各种状态转移方程搞得晕头转向。直到某天深夜，当我反复推导这三个基础问题后，突然有种豁然开朗的感觉。这三个题目就像俄罗斯套娃，层层递进地揭示了DP的本质：将复杂问题分解为重叠子问题，通过记忆化存储避免重复计算。

2. 509. 斐波那契数：动态规划的Hello World

2.1 问题定义与暴力递归解法

斐波那契数列的定义简单明了：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2), n >= 2

最直观的解法是递归：

def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)

但这种方法存在严重的效率问题。以计算fib(5)为例，调用树如下：

fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1)

可以看到fib(3)被计算了两次，fib(2)被计算了三次。时间复杂度达到O(2^n)，空间复杂度O(n)。

2.2 记忆化搜索与动态规划优化

这就是动态规划要解决的核心问题——重叠子问题。我们可以通过两种方式优化：

方法一：记忆化递归（自顶向下）

memo = {0:0, 1:1} def fib(n): if n not in memo: memo[n] = fib(n-1) + fib(n-2) return memo[n]

方法二：迭代法（自底向上）

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)，空间复杂度O(n)。但我们可以进一步优化空间：

def fib(n): if n <= 1: return n prev, curr = 0, 1 for _ in range(2, n+1): prev, curr = curr, prev + curr return curr

这个版本空间复杂度仅为O(1)，是面试中最受青睐的写法。

关键理解：动态规划的核心在于发现重叠子问题并避免重复计算。斐波那契数列是理解这一概念的完美起点。

3. 70. 爬楼梯：斐波那契的变种

3.1 问题转化与状态定义

爬楼梯问题描述：每次可以爬1或2个台阶，有多少种方法爬到第n阶？

仔细分析会发现，这与斐波那契数列惊人地相似：

• 到达第n阶的方法数 = 到达第n-1阶的方法数（最后一步爬1阶） + 到达第n-2阶的方法数（最后一步爬2阶）

状态转移方程： dp[n] = dp[n-1] + dp[n-2]

初始条件： dp[0] = 1 (地面算作一种方法) dp[1] = 1

3.2 实现与优化

直接套用斐波那契的优化思路：

def climbStairs(n): if n <= 2: return n prev, curr = 1, 2 for _ in range(3, n+1): prev, curr = curr, prev + curr return curr

3.3 扩展思考：如果每次可以爬1、2或3阶呢？

此时状态转移方程变为： dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

这种变种问题在面试中经常出现，考察的是对DP思想的理解深度而非死记硬背。

4. 746. 使用最小花费爬楼梯：引入代价因素

4.1 问题升级与状态重新定义

现在的问题变为：每级台阶都有一个cost[i]，支付该费用后可以选择爬1或2阶。可以从0或1阶开始，求达到顶部的最小花费。

关键点在于：

1. 到达i阶的最小花费 = min(到达i-1阶的最小花费 + cost[i-1], 到达i-2阶的最小花费 + cost[i-2])
2. 最终目标是到达第n阶（即cost数组长度+1）

状态转移方程： dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

初始条件： dp[0] = 0 (可以从0阶开始，初始无花费) dp[1] = 0 (也可以从1阶开始)

4.2 代码实现与空间优化

基础DP解法：

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): prev, curr = 0, 0 for i in range(2, len(cost)+1): prev, curr = curr, min(curr + cost[i-1], prev + cost[i-2]) return curr

4.3 常见错误与边界情况

1. 错误地将dp[1]初始化为cost[0]：忽略了可以从1阶直接开始的情况
2. 忘记最终目标是n阶而非n-1阶
3. 对于空数组或单元素数组的处理

5. 动态规划解题的通用思维框架

通过这三个经典问题，我们可以总结出解决DP问题的通用步骤：

1. 定义状态：明确dp[i]表示什么（斐波那契中的F(i)，爬楼梯中的方法数，最小花费中的累计成本）
2. 确定转移方程：如何用之前的状态推导当前状态
3. 设置初始条件：dp[0]、dp[1]等的值
4. 考虑优化：是否可以压缩空间复杂度
5. 处理边界：n=0,1等特殊情况

在实际面试中，我建议按照以下顺序思考：

1. 先想暴力递归解法
2. 画出递归树，发现重叠子问题
3. 改用记忆化搜索
4. 转化为迭代形式的DP
5. 最后考虑空间优化

6. 从这三个问题到更复杂的DP问题

掌握了这三个基础问题后，可以尝试解决更复杂的DP问题：

• 背包问题（01背包、完全背包）
• 最长公共子序列
• 股票买卖问题
• 打家劫舍问题

这些问题的核心思想都是一致的——定义状态、找到状态转移关系、处理初始条件和边界情况。

我在刷题过程中发现，很多DP难题其实都是这几个基础问题的变种或组合。比如"打家劫舍"问题就融合了爬楼梯和最小花费的思想。

7. 算法训练中的实战建议

1. 不要死记硬背：理解状态转移的本质比记住代码更重要
2. 画图辅助：对于新问题，先画递归树或状态转移图
3. 循序渐进：从一维DP开始，逐步过渡到二维DP
4. 反复练习：这三个基础问题建议手写实现5遍以上，直到能闭眼写出最优解
5. 对比分析：比较这三个问题的异同点，理解DP的灵活性

在代码随想录的训练营中，我发现很多同学在DP问题上容易犯两个极端错误：要么过度依赖记忆，要么完全回避DP。实际上，DP就像游泳，需要在理解原理的基础上通过大量练习来培养直觉。