LeetCode 풀기 - 70. Climbing Stairs

70. Climbing Stairs

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

Climbing Stairs - LeetCode

 

문제)

솔루션1)

• 동적 계획법 풀이

class Solution:
    
    def climbStairs(self, n: int) -> int:
        '''
        f(0) = 0
        f(1) = 1
        f(2) = 2
        f(3) = f(2) + f(1)
        ...
        f(n) = f(n-1) + (n-2)
        
        '''
        
        fn = [0, 1, 2]
        
        # bottom up
        for i in range(3, n+1):
            fn.append(fn[i-1] + fn[i-2])
        return fn[n]

솔루션2)

class Solution:
    
    def climbStairs(self, n: int) -> int:       
        if n <=2:
            return n
        
        a, b, c = 0, 1, 2
        
        # bottom up
        for i in range(3, n+1):
            a, b = b, c
            c = a + b
            
        return c

솔루션3)

• 백트래킹 + 메모이제이션

class Solution:
    
    @lru_cache(maxsize=128)
    def climbStairs(self, n: int) -> int:       
        # backtracking
        
        if n == 0 or n == 1: 
            return 1
        
        return self.climbStairs(n-1) + self.climbStairs(n-2)