题目描述
每次能爬 1 或 2 阶，爬到第 n 阶共有几种不同方法？
思路解析
最直接的想法是递归 f(n)=f(n-1)+f(n-2)。但 f(5) 要 f(4) 和 f(3)，f(4) 又要 f(3) 和 f(2)……同一个 f(3)、f(2) 会被算很多遍，n 一大调用数指数膨胀。慢就慢在重复子问题。
想到第 i 阶，最后一步要么从 i-1 阶跨 1 阶上来，要么从 i-2 阶跨 2 阶上来，所以 dp[i] = dp[i-1] + dp[i-2]。为什么能记表？每个 dp[i] 只算一次存进表，后面直接查，把递归里重复算的子问题省成一次——这就是「状态转移」加「记表」。
建表：表固定 1 行 6 列，dp[i] 表示「到第 i 阶有几种走法」。咱从左到右把这一行填满。
地基 · dp[0]：第 0 阶就是起点，「待在原地不动」算 1 种走法，dp[0] = 1。这是不依赖别人的地基。
地基 · dp[1]：到第 1 阶只有 1 种走法(跨 1 阶)，dp[1] = 1。dp[0]、dp[1] 是两块「地基」，直接给定，不用算。
dp[2]：从这一格起，每个值都等于前两格之和：dp[2] = dp[1] + dp[0] = 1 + 1 = 2。两块依赖格(dep)亮起来。
dp[3]：依赖格往右滑一格：dp[3] = dp[2] + dp[1] = 2 + 1 = 3。注意 f(3) 在递归里要算好几遍，这里只算这一次。
dp[4]：同样规则：dp[4] = dp[3] + dp[2] = 3 + 2 = 5。
dp[5]：dp[5] = dp[4] + dp[3] = 5 + 3 = 8。最后一格填好了。
答案 = 最后一格：表格最后一格 dp[5] = 8 就是答案。整行 1、1、2、3、5、8 每个值都只算了一次。
1、1、2、3、5、8——每个数都是前两个之和。这就是斐波那契，DP 的最佳入门例子。
找到「当前格和前面格的关系」，再从地基填到目标——这就是 DP。打家劫舍、泰波那契都是同一套。
参考代码（Python）
1def climbStairs(self, n):
2 dp = [0] * (n + 1)
3 dp[0] = 1 # 地基
4 dp[1] = 1 # 地基
5 for i in range(2, n + 1):
6 dp[i] = dp[i-1] + dp[i-2] # 状态转移
7 return dp[n]复杂度分析
- 时间复杂度：O(n) —— 只从 2 到 n 填一遍表，每格算一次
- 空间复杂度：O(n) —— 一张长 n+1 的表；只依赖前两项，可压成两个变量降到 O(1)
套路模板
所有 DP 都是这四步：定义、递推、base、遍历顺序。当填空题做。
1# 1.定义 dp[i] 含义 2.写递推 3.定 base 4.定遍历顺序
2dp = [0]*(n+1)
3dp[0], dp[1] = 1, 1 # base case
4for i in range(2, n+1):
5 dp[i] = dp[i-1] + dp[i-2] # 递推
6return dp[n]易错点
- 错误写法：base 写成 dp[1]=1、dp[2]=2 但不开够空间 → 正确写法：初值 dp[0]=1、dp[1]=1，遍历从 2 开始（base 选错或下标对不上，整行会整体错位，答案全错）
- 错误写法：遍历方向写反(从大到小) → 正确写法：从小到大填，后面依赖前面（算 dp[i] 时 dp[i-1]、dp[i-2] 必须已经有值）
- 错误写法：n 很小时 dp[1] 越界 → 正确写法：先保证表长 n+1、按需特判 n<=1（否则 n=0/1 时访问不存在的格子）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。