[LeetCode] 70. Climbing Stairs

Problem : https://leetcode.com/problems/climbing-stairs/

Let  stairs(x) = steps to reach stair x.

We can either reach to stair x by climb 1 step from stair x - 1, or climb 2 steps from stair x - 2. 

stairs(x) = stair(x-1) + stair(x-2)

Obviously,  stair(1) = 1 and stair(2) = 2

Below is a memorization based implementation.

Time Complexity : O ( N )

The top-down solution:

class Solution:
    def climbStairs(self, n: int) -> int:
        
        @cache
        def stairs(x): 
            return stairs(x-1) + stairs(x-2) if x > 2 else x
        
        return stairs(n)

The bottom-up solution:

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 0, 1    
        for _ in range(n):
            a, b = b, a + b
        
        return b

Edited on 10/05/2021. Update the top-down and buttom-up solutions.