题目描述：leetcode
有一段楼梯，总共有 n 级台阶。
每次你可以爬 1 级或者 2 级。
问：从第 0 级（地面）出发，爬到第 n 级，一共有多少种不同的走法？
示例：
n = 2，答案是 2：
1 + 1
2
n = 3，答案是 3：
1 + 1 + 1
1 + 2
2 + 1
leetcode
约束：1 <= n <= 45。leetcode
这道题是 LeetCode 非常经典的一维动态规划题，也是入门斐波那契型 DP 的好例子。leetcode
初始思路：从「走的步数」出发（错误思路）
一开始容易这样想：
定义 dp[i] 表示「走了 i 步之后，总共爬了多少级台阶」。
每一步可以走 1 或 2 级，于是尝试在循环里不断累加：
每次选择 1 或 2 作为步长。
如果刚好走到 n，就认为找到一种方案。
这个思路的问题：
dp[i] 存的是「位置」（台阶数），题目需要的是「方案数」，状态含义不匹配。
转移类似写成 dp[i] = dp[i - 1] + choice，其中 choice 是 1 或 2，是步长，不是方案数量。
为了数方案，再去判断 if (dp[i] == n) 可能性++，会导致枚举路径、逻辑复杂且容易漏解。
总结：
把「位置」和「方案数」混在一个状态里，是这个方向的根本问题。
想用 DP 解决计数类问题，dp[i] 更适合作为「第 i 个状态 有多少种方案」。
正确的状态定义：到达某一级的方案数
更自然的定义是：
dp[i] 表示「到达第 i 级台阶，有多少种不同的走法」。
这样定义之后，题目问的「到达第 n 级有多少种走法」，就可以直接对应到 dp[n]。
接下来思考转移：
想到达第 i 级台阶，上一步可能在哪？
如果上一步走 1 级，那上一步在第 i - 1 级；
如果上一步走 2 级，那上一步在第 i - 2 级。
所以，到达第 i 级的所有方案，就是：
所有「先到第 i - 1 级，再走 1 级」的方案
加上所有「先到第 i - 2 级，再走 2 级」的方案
于是得到经典转移方程：
dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i - 1] + dp[i - 2]dp[i]=dp[i−1]+dp[i−2]
这就是一个标准的斐波那契数列形式。leetcode
初始条件的两种写法
有了转移方程，还需要考虑边界（初始状态）。常见有两种写法。
写法 A：从 0 级开始递推
把「地面」当作第 0 级台阶：
dp[0] = 1
含义：在第 0 级台阶，有 1 种方式——什么都不做。
dp[1] = 1
含义：到达第 1 级，只能从第 0 级走 1 步上来，所以也只有 1 种方式。
然后从 i = 2 开始，用转移方程递推到 n：
dp[i]=dp[i−1]+dp[i−2],i≥2dp[i] = dp[i - 1] + dp[i - 2], \quad i \ge 2dp[i]=dp[i−1]+dp[i−2],i≥2
最终答案是 dp[n]。leetcode
这种写法的特点：
数组大小一般开到 n + 1，下标从 0 到 n 都有意义。
边界统一自然，和斐波那契常见写法类似。
写法 B：从 1 级开始递推
也可以从 1 级台阶开始定义边界：
dp[1] = 1：到第 1 级只有「1」这一种走法。
dp[2] = 2：到第 2 级有两种走法：「1+1」和「2」。
然后从 i = 3 开始，使用同样的转移方程：
dp[i]=dp[i−1]+dp[i−2],i≥3dp[i] = dp[i - 1] + dp[i - 2], \quad i \ge 3dp[i]=dp[i−1]+dp[i−2],i≥3
最终同样输出 dp[n]。
这种写法的特点：
不直接用 dp[0]，只在 1 到 n 的范围内活动。
对于有些人来说，从「第 1 级」开始会更直观。
注意：
如果采用写法 B，代码里即使有 dp[0]，它也不会被用到，所以它取 0 或 1，在实际计算中都不影响结果，但从语义上讲，一般依然认为「到第 0 级有 1 种方式」。
一维 DP 解法总结
将上面的讨论整理成统一的 DP 思路：
状态定义：
dp[i] 表示「到达第 i 级台阶的不同走法数量」。
转移方程：
dp[i] = dp[i - 1] + dp[i - 2]，因为上一步只能从 i - 1（走 1 级）或 i - 2（走 2 级）来。
初始条件（以写法 A 为例）：
dp[0] = 1
dp[1] = 1
计算顺序：
从小到大，依次计算 dp[2], dp[3], …, dp[n]。
答案：
返回 dp[n]。leetcode
时间复杂度和空间复杂度：
时间复杂度：O(n)，只需要一遍循环。
空间复杂度：
用数组是 O(n)；
由于每次只依赖 dp[i-1] 和 dp[i-2]，可以只用两个变量滚动，空间优化到 O(1)。leetcode
一点延伸：为什么是斐波那契
从递推关系可以看出：
dp[1] = 1
dp[2] = 2
dp[3] = dp[2] + dp[1] = 3
dp[4] = dp[3] + dp[2] = 5
dp[5] = dp[4] + dp[3] = 8
……
这正是斐波那契数列平移后的形式：每一项等于前两项之和。leetcode
这类题的关键点在于：
把「路径数」定义成状态，而不是「当前位置」；
搞清楚「当前状态」能由哪些「前一个状态」一步转移过来；
将所有可能的前驱状态的方案数累加起来，构成当前的方案数。
掌握了这道题，之后看「跳台阶」「爬楼梯变种」「一步可以跳 1/2/3 级」等等题目，就会自然地套用：
「能从哪些位置跳过来」
「把这些位置的方案数加起来」。
https://leetcode.com/problems/climbing-stairs/?envType=study-plan-v2&envId=top-interview-150
