题目描述
每次能爬 1 或 2 阶，爬到第 n 阶共有几种不同方法？
n = 5
输出 = 8
思路解析
直接写 f(n)=f(n-1)+f(n-2) 的递归，会把同一个 f(3)、f(2) 算很多遍，n 一大就极慢。咱改成「填表」，每个值只算一次。
想到第 i 阶，最后一步要么从 i-1 阶跨 1 阶上来，要么从 i-2 阶跨 2 阶上来。所以方法数 = 这两者之和。这就是「状态转移」。
建表：dp[i] 表示「到第 i 阶有几种走法」。咱要把这一行从左到右填满。
边界 · 第 1 阶：到第 1 阶只有 1 种走法（跨 1 阶）。dp[1] = 1。
边界 · 第 2 阶：到第 2 阶有 2 种：1+1，或者直接跨 2。dp[2] = 2。这两个是「地基」，不用算。
第 3 阶：到第 3 阶 = 到第 2 阶(2 种) + 到第 1 阶(1 种) = 3。把前两格相加填进来。
第 4 阶：同样规则：dp[4] = dp[3] + dp[2] = 3 + 2 = 5。
第 5 阶：dp[5] = dp[4] + dp[3] = 5 + 3 = 8。
答案：表格最后一格 dp[5] = 8 就是答案。每个值只算了一次。
1、2、3、5、8——每个数都是前两个之和。这就是斐波那契，DP 的最佳入门例子。
找到「当前格和前面格的关系」，再从地基填到目标——这就是 DP。打家劫舍、泰波那契都是同一套。
参考代码（Python）
Python
1def climbStairs(self, n):
2 if n == 1: return 1
3 if n == 2: return 2
4 memo = [0] * (n + 1)
5 memo[1] = 1 # 地基
6 memo[2] = 2 # 地基
7 for i in range(3, n + 1):
8 memo[i] = memo[i-1] + memo[i-2] # 状态转移
9 return memo[n]复杂度分析
- 时间复杂度：O(n) —— 填 n 个格子
- 空间复杂度：O(n) —— 一张表；其实可压成两个变量
套路模板
所有 DP 都是这四步：定义、递推、base、遍历顺序。当填空题做。
Python
1# 1.定义 dp[i] 含义 2.写递推 3.定 base 4.定遍历顺序
2dp = [0]*(n+1)
3dp[1], dp[2] = 1, 2 # base case
4for i in range(3, n+1):
5 dp[i] = dp[i-1] + dp[i-2] # 递推
6return dp[n]易错点
- ❌ n=1/n=2 不特判 → ✅ 先处理 n<=2 的边界（否则 dp[2] 在 n=1 时越界）
- ❌ 遍历方向写反 → ✅ 从小到大填（后面依赖前面）（算 dp[i] 时 dp[i-1] 必须已有值）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。