1 / 4思路
Climbing Stairs
思路
到达第 n 级,只能从第 n-1 级走一步,或从第 n-2 级走两步。因此 f(n) = f(n-1) + f(n-2),即斐波那契数列。只需保留前两项,空间降为 O(1)。
复杂度
- 时间 O(n):从 1 到 n 递推。
- 空间 O(1):两个变量。
代码
- Python
- TypeScript
def climb_stairs(n: int) -> int:
previous, current = 1, 1
for _ in range(n - 1):
previous, current = current, previous + current
return current
function climbStairs(n: number): number {
let previous = 1;
let current = 1;
for (let step = 1; step < n; step += 1) {
[previous, current] = [current, previous + current];
}
return current;
}
边界
- n = 1:只有一种走法,返回 1。
- n 很大:结果超过 2^53 时 TS 的 number 会丢精度;比赛范围通常不触发,工程里应换 BigInt。
- 初始值不能都设成 0,否则 n = 1 时返回 0。