易中 · DP 入门
爬楼梯
从「最后一步」想，而不是从第一步想：站上第 n 级，你必然来自第 n−1 或 n−2 级，而这两类走法的最后一步互不相同。这一句话就是整个算法。
一句话答案ways(n) = ways(n-1) + ways(n-2)，其中 ways(1) = 1、ways(2) = 2 —— 只用两个变量一路滚上去。
题目
输入: 一个整数 n（1 ≤ n ≤ 40），楼梯的级数。
输出: 每次跨 1 或 2 级、走到第 n 级的不同走法总数。
样例:
| 输入 | 输出 |
|---|---|
3 | 3 |
5 | 8 |
n = 3 时的三种走法是 1+1+1、1+2、2+1 —— 步骤的先后算不同走法，所以 2+1 和 1+2 不是同一条路。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 从最后一步想
每条到第 n 级的路，最后一步要么是从 n−1 跨 1 级，要么是从 n−2 跨 2 级。这两类路互不重叠，合起来又是全部 —— 所以 ways(n) = ways(n-1) + ways(n-2)。当一段论证以「看最后一步」开头时，附近多半藏着动态规划。
提示 2 — 把边界钉死
ways(1) = 1（一种：1）、ways(2) = 2（1+1 或 2）。先把它们写出来，再用最小的输入手算对一下 —— 这题的大多数错误答案来自边界差一，而不是递推式写错。
提示 3 — 两个变量就够
递推式只回头看一步和两步，所以留着 a = ways(k-1) 和 b = ways(k)，循环里滚上去：c = a + b; a = b; b = c;。不用数组、不用递归 —— 也躲开了朴素递归版本的指数爆炸。
题解（先自己试试！）
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a = 1, b = 2; // ways(1), ways(2)
if (n == 1) { cout << 1 << endl; return 0; }
for (int k = 3; k <= n; k++) {
long long c = a + b;
a = b;
b = c;
}
cout << b << endl;
return 0;
}你刚写完第一个动态规划：递推式、边界、自底向上填表。同样的三件套解 斐波那契（字面上就是同一列数），以后还会解 最小路径和 这样的二维表。值得留下的习惯：从最后一步推出递推式，然后一路信任它。
深度解析
为什么这样做对
问最后一步,而不是第一步:到第 n 级的每条路,要么从 n−1 跨 1 级来,要么从 n−2 跨 2 级来,这两类不重叠也不遗漏。于是 ways(n) = ways(n-1) + ways(n-2) —— 「用更小的已知答案拼出当前答案」,这就是 DP 的定义。
代价
两个滚动变量,O(n) 时间、O(1) 空间:40 级楼梯只是 38 次加法。朴素递归则要约 2^n 次调用 —— n = 40 时超过十亿次,绝大多数是同一批值的重复计算。
常见错法
- 边界:
ways(1) = 1、ways(2) = 2(一次跨两步是一种走法,不是两种)。把种子写成 1 和 1,后面每个答案都会整体偏小。 - 朴素的无记忆化递归是指数级的 —— n = 40 附近真判题必超时。滚动对是同一套数学,没有爆炸。另外 n 超过 45 后答案超出 32 位 int:用
long long。 ways(0) = 1(站着不动)也是合法约定 —— 但代码里混用两种约定就会重复计数。选定一种,让循环和它对齐。
记住这两句
- DP = 最后一步 + 更小的答案;从终点那一步推出来。
- 递推式只回看 1–2 步时,两个滚动变量就能替掉整个数组。
🐞 这段是错的 —— 点开,亲手让它挂一次
把种子写成 1 和 1 —— n > 1 的答案全都小了一号
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a = 1, b = 1; // bug: ways(2) should be 2
if (n == 1) { cout << 1 << endl; return 0; }
for (int k = 3; k <= n; k++) {
long long c = a + b;
a = b;
b = c;
}
cout << b << endl;
return 0;
}