Skip to main content

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):两个变量。

代码​

def climb_stairs(n: int) -> int:
previous, current = 1, 1
for _ in range(n - 1):
previous, current = current, previous + current
return current

边界​

  • n = 1:只有一种走法,返回 1。
  • n 很大:结果超过 2^53 时 TS 的 number 会丢精度;比赛范围通常不触发,工程里应换 BigInt。
  • 初始值不能都设成 0,否则 n = 1 时返回 0。