Climbing Stairs
这道题表面上看非常简单： 一次可以爬 1 个台阶或者 2 个台阶，问爬到第 n 阶一共有多少种不同的方法。
但它之所以经典，不是因为题目难，而是因为它非常适合帮助初学者理解动态规划里最重要的几个概念：
-
状态到底怎么定义
-
状态转移方程是怎么推出来的
-
为什么有些动态规划题最后可以优化到只用几个变量
你给出的这份 Java 代码，就是这道题非常经典的一种写法：
动态规划 + 空间优化
它没有额外开数组，而是只用两个变量不断滚动更新答案。 这种写法非常简洁，也非常适合作为动态规划入门模板来掌握。
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
假设你正在爬楼梯。
需要 n 阶你才能到达楼顶。 每次你可以爬：
-
1个台阶 -
或者
2个台阶
问你一共有多少种不同的方法可以爬到楼顶。
例如：
当 n = 1
只有一种方法：
1
当 n = 2
有两种方法：
1 + 1
2
当 n = 3
有三种方法：
1 + 1 + 1
1 + 2
2 + 1
所以答案是 3。
这道题看起来像是在数路径，但本质上其实是一道非常标准的动态规划题。
示例
示例 1
输入：n = 2
输出：2
因为可以这样爬：
-
1 + 1 -
2
所以共有两种。
示例 2
输入：n = 3
输出：3
因为可以这样爬：
-
1 + 1 + 1 -
1 + 2 -
2 + 1
所以共有三种。
最直接的想法是什么？
如果最开始不去想动态规划，一个很自然的思路可能是：
-
要到达第
n阶 -
最后一步可能是从第
n-1阶爬 1 步上来 -
也可能是从第
n-2阶爬 2 步上来
于是你会发现，到达第 n 阶的方法数，其实和前两个状态有关。
这已经非常接近动态规划了。
如果再往前推一下：
-
到达第
n-1阶的方法数也已经算好了 -
到达第
n-2阶的方法数也已经算好了
那么到达第 n 阶的方法数，就是这两者之和。
这就是这道题的核心。
核心思路：状态转移
我们可以定义：
dp[i] = 爬到第 i 阶的方法数
那么第 i 阶是怎么来的？
只有两种可能：
情况 1：最后一步爬 1 阶
那前面一定已经站在第 i - 1 阶。 所以这种情况的方法数是：
dp[i - 1]
情况 2：最后一步爬 2 阶
那前面一定已经站在第 i - 2 阶。 所以这种情况的方法数是：
dp[i - 2]
因此状态转移方程就是：
dp[i] = dp[i - 1] + dp[i - 2]
这和斐波那契数列的递推关系非常像，所以很多人也会把这道题看成“斐波那契模板题”。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public int climbStairs(int n) {
int n1 = 1, n2 = 2;
// 边界情况
if (n == 1) return n1;
if (n == 2) return n2;
for (int i = 3; i <= n; i++) {
int t = n2;
n2 = n1 + n2;
n1 = t;
}
return n2;
}
}
代码拆解
这段代码虽然很短，但它其实已经把动态规划的核心思想完整体现出来了。 下面一步一步来看。
1. 为什么 n = 1 和 n = 2 要单独处理？
int n1 = 1, n2 = 2;
if (n == 1) return n1;
if (n == 2) return n2;
因为这是这道题最基础的两个初始状态。
当 n = 1
只有一种爬法：
1
所以：
dp[1] = 1
当 n = 2
有两种爬法：
1 + 1
2
所以：
dp[2] = 2
而后面的所有状态，都建立在这两个初始值之上。
所以这两个边界必须先确定好。
2. 为什么循环从 3 开始？
for (int i = 3; i <= n; i++)
因为：
-
dp[1]已经知道 -
dp[2]也已经知道
所以从第 3 阶开始，我们就可以利用状态转移方程去不断往后推。
例如：
dp[3] = dp[2] + dp[1]
dp[4] = dp[3] + dp[2]
dp[5] = dp[4] + dp[3]
这就是循环从 3 开始的原因。
3. n1 和 n2 分别表示什么？
int n1 = 1, n2 = 2;
在这份代码里：
-
n1表示前两个状态中的较小那个 -
n2表示当前更靠后的那个状态
更准确一点来说，在循环过程中它们的含义是：
-
n1：上上一个状态 -
n2：上一个状态
也就是：
n1 = dp[i - 2]
n2 = dp[i - 1]
这样当我们要计算当前状态时，就可以直接写成：
dp[i] = n1 + n2
这就是空间优化后的动态规划写法。
4. 为什么更新写成这样？
int t = n2;
n2 = n1 + n2;
n1 = t;
这是整段代码最核心的部分。
假设当前循环要计算的是第 i 阶的方法数，那么：
-
原来的
n1 = dp[i - 2] -
原来的
n2 = dp[i - 1]
那么当前答案应该是：
dp[i] = dp[i - 1] + dp[i - 2]
也就是：
n2 = n1 + n2;
但更新之后，还要为下一轮循环做准备：
-
下一轮的
n1应该变成当前的旧n2 -
下一轮的
n2应该变成当前新算出来的值
所以先用一个临时变量 t 把旧的 n2 保存下来：
int t = n2;
然后：
-
n2 = n1 + n2：算出当前新状态 -
n1 = t：把旧的n2移到n1
这样一来，两个变量就完成了“向前滚动”。
手动模拟一遍
我们用 n = 5 来走一遍。
已知：
dp[1] = 1
dp[2] = 2
代码初始：
n1 = 1
n2 = 2
第一次循环：i = 3
t = 2
n2 = 1 + 2 = 3
n1 = 2
此时：
n1 = 2
n2 = 3
对应：
dp[2] = 2
dp[3] = 3
第二次循环：i = 4
t = 3
n2 = 2 + 3 = 5
n1 = 3
此时：
n1 = 3
n2 = 5
对应：
dp[3] = 3
dp[4] = 5
第三次循环：i = 5
t = 5
n2 = 3 + 5 = 8
n1 = 5
此时：
n2 = 8
所以答案是：
8
也就是说，爬到第 5 阶一共有 8 种方法。
为什么这个方法是正确的？
因为对任意第 i 阶来说，最后一步只有两种可能：
-
从第
i-1阶爬 1 步上来 -
从第
i-2阶爬 2 步上来
这两种情况互不重叠，而且覆盖了所有可能性。 所以总方法数一定就是它们之和：
dp[i] = dp[i - 1] + dp[i - 2]
而你这份代码做的事情，本质上就是按照这个公式，从小到大把答案推出来。
由于每一步只依赖前两个状态，所以根本不需要完整的 dp 数组，只需要两个变量就够了。
因此，这个算法在逻辑上是完全正确的。
和斐波那契数列有什么关系？
这道题和斐波那契数列非常像。
如果你写出前几项：
-
dp[1] = 1 -
dp[2] = 2 -
dp[3] = 3 -
dp[4] = 5 -
dp[5] = 8 -
dp[6] = 13
你会发现，它就是一个“稍微平移过的斐波那契数列”。
所以很多人会把这题当成动态规划里的“斐波那契模板题”。
不过要注意的是，刷题时最好不要只记“它像斐波那契”，更重要的是理解它为什么满足这个递推关系。 因为只有把“最后一步来自哪里”这件事想明白，后面遇到类似问题时你才能自己推出状态转移。
为什么不需要 dp 数组？
如果按最传统的动态规划写法，我们可以写成：
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
这样当然也可以。
但观察状态转移式：
dp[i] 只依赖 dp[i-1] 和 dp[i-2]
说明更早之前的状态值根本不需要保留。 所以就可以把数组优化成两个变量。
这就是所谓的 状态压缩。
你这份代码正是状态压缩后的版本：
-
时间复杂度不变
-
空间复杂度更低
-
代码也更简洁
复杂度分析
时间复杂度
循环从 3 一直到 n，所以时间复杂度是：
O(n)
空间复杂度
只使用了几个额外变量：
-
n1 -
n2 -
t
所以空间复杂度是：
O(1)
这也是这道题空间优化写法的一个重要优势。
这道题真正想考什么？
这道题表面上是在爬楼梯，但本质上考察的是动态规划最基础的东西。
第一，能不能定义清楚状态
你要明确：
dp[i]
到底表示什么。
在这题里，它表示：
爬到第 i 阶的方法总数
一旦状态定义清楚，递推关系自然就能推出来。
第二，能不能从“最后一步”入手思考
很多动态规划题都可以用这种方法：
-
不直接想“前面所有情况”
-
而是想“最后一步怎么来的”
这会让问题结构一下子清晰很多。
第三，能不能做状态压缩
当状态转移只依赖前面有限几个状态时，就可以考虑把数组压缩成变量。 这是动态规划里非常常见的优化技巧。
和“不同路径”“最小路径和”有什么区别？
这三道题都常被拿来做 DP 入门对比。
爬楼梯
一维 DP。 状态转移：
dp[i] = dp[i-1] + dp[i-2]
不同路径
二维 DP。 状态转移：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
最小路径和
二维 DP。 状态转移：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
你会发现，它们的共同点非常明显：
-
都是从较小子问题推到较大问题
-
都依赖前面的状态
-
都能通过状态定义写出递推关系
所以“爬楼梯”其实就是最适合用来练动态规划基本功的一道题。
总结
这道题的核心思想可以概括成一句话：
到达第 n 阶的方法数，等于到达第 n-1 阶的方法数加上到达第 n-2 阶的方法数。
具体步骤就是：
-
定义
dp[i]表示爬到第i阶的方法数 -
得到状态转移方程：
dp[i] = dp[i - 1] + dp[i - 2]
-
初始化：
dp[1] = 1
dp[2] = 2
-
由于每一步只依赖前两个状态，所以用两个变量进行空间优化
-
最终返回答案
这样就能在：
O(n)
的时间复杂度和：
O(1)
的空间复杂度下解决问题。
这是一道非常经典、也非常值得反复理解的动态规划题。 因为它会让你真正体会到：
-
状态定义的重要性
-
最后一步分析法的威力
-
状态转移方程是如何自然推出来的
-
动态规划并不一定需要数组，有时两个变量就够了
把这道题真正吃透之后，再去看：
-
打家劫舍
-
斐波那契数列
-
最小花费爬楼梯
-
解码方法
这些一维 DP 题时，你会明显更容易抓住套路。
