LC 0070 [E] Climbing Stairs - ALawliet/algorithms GitHub Wiki
prereq: Fibonacci Number
if we're at stair 5, we could only have come from stair 5-1 = 4 (+1) or stair 5-2 = 3 (+2), so how many ways were there to get to stair 4 and 3?
class Solution:
@cache
def climbStairs(self, n: int) -> int: # n >= 1
if n == 1: return 1 # 1 way to make 1, take a step of 1
if n == 2: return 2 # 2 ways to make 0, take 2 steps of 1 or take 1 step of 2
return self.climbStairs(n-1) + self.climbStairs(n-2)
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1: return 1
T = [0 for _ in range(n)]
T[0] = 1
T[1] = 2
for i in range(2, n):
T[i] += T[i-1]
T[i] += T[i-2]
return T[-1]
class Solution:
def climbStairs(self, n: int) -> int:
one, two = 1, 1
for _ in range(n - 1):
temp = one
one = one + two
two = temp
return one