Climbing Stairs

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

Climbing Stairs - LeetCode

계단을 올라갈 때 하나 혹은 둘씩 올라간다고 할 때 경우의 수가 몇이나 되는지 헤아리는 문제. 필연적으로 말단으로 갈 수록 경우의 수가 겹친다. 따라서 동적 프로그래밍 기법으로 계산을 반복하지 않도록 해야 한다.

 

 

class Solution:
    def climbStairs(self, n: int, cache = None) -> int:
        # 기본 경우의 수. 계단이 1개이면 1개의 경우(한칸만 가고 끝), 2개이면 2개의 경우가 있다(1칸씩 두 번 또는 2칸으로 한 번)
        if cache is None:
            cache = {
                0 : 0,
                1 : 1,
                2 : 2
            }
            
        if n in cache:
            return cache[ n ]
        
        # 한칸과 두칸으로 시작했을 경우의 수를 더한다
        result = self.climbStairs( n - 1, cache ) + self.climbStairs( n - 2, cache )
        cache[ n ] = result
        
        return result