Grammarly VO 面试真题解析：Climbing Stairs 动态规划

Climbing Stairs

Description

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

You can assume n is greater than 0.

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

这道题本质上是经典的动态规划计数问题：到达第 n 级台阶的方法数，只取决于前一级和前两级的方案数，因为最后一步只能走 1 级或 2 级。因此可以用递推式 dp[i] = dp[i-1] + dp[i-2]，也可以用两个变量滚动维护，空间优化到 O(1)。样例 n=2 输出 2、n=3 输出 3，正好对应斐波那契式增长。