70. Climbing Stairs
https://leetcode.com/problems/climbing-stairs/
solution
# 空间优化写法: 状态转移过程中只依赖过去两步
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
prev = 1
cur = 2
for i in range(3, n + 1):
dp = prev + cur
prev = cur
cur = dp
return cur
时间复杂度:O(n) 空间复杂度:O(1)
Last updated