GESP 六级 · GESP202609 C++ 六级 第 13 题

下面代码计算走到第 n 级台阶的方法数，每次可以走 1 级或 2 级。横线处应填写（　　）。

int ways(int n) {
if (n <= 2)
return n;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i)
dp[i] = __________________________;
return dp[n];
}

看到"走1级或2级"立刻想到斐波那契递推。核心观察：第i级只能从i-1或i-2跳过来，所以dp[i] = dp[i-1] + dp[i-2]。边界是dp[1]=1, dp[2]=2，循环从3填到n即可。这类题通法是：先找状态转移方程，再确定初始值，最后用循环或递归填表。

选项A把dp[i-1]当"到i-1的步数"却加1，混淆了"到达i-1的方法数"和"从i-1再走1步"；C在dp[i-2]基础上硬加2，忽略了从i-2跳2步本身就是一种方法；D用乘法假设每个i-1路径都能接2步，完全错误。最阴险的是边界：dp[2]=2是题目给的，但dp[1]=1必须手动设，很多人会漏填dp[1]导致循环从3开始就错。

1. 考纲定位

本题考查 GESP 六级《算法与数据结构》模块的动态规划递推，属于"计数问题"的经典考法。命题人卡住的是"状态转移方程"的识别——多数考生能写出斐波那契，但容易把"到 i-1 的方法数"和"从 i-1 再走 1 步"混为一谈。这道题就是专门测试你是否理解 dp[i-1] 已经包含了所有到达 i-1 的路径，而不是"从 i-1 出发还能走几步"。

2. 解题思维

看到"走 1 级或 2 级"立刻想到斐波那契递推。核心观察：第 i 级只能从 i-1 或 i-2 跳过来，所以 dp[i] = dp[i-1] + dp[i-2]。边界是 dp[1]=1, dp[2]=2，循环从 3 填到 n 即可。这类题通法是：先找状态转移方程，再确定初始值，最后用循环或递归填表。