리트코드 70번 Climbing Stairs (python)

Problem

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

Solution

내 풀이 - 중복 조합

from collections import defaultdict

class Solution:

    def climbStairs(self, n: int) -> int:
        factorial_dict = defaultdict(int)

        def factorial(x):
            if x <= 1:
                return 1
            elif x not in factorial_dict.keys():
                factorial_dict[x] = x * factorial(x - 1)
            return factorial_dict[x]

        # n = 2 * a + 1 * b
        a, b = n // 2, n % 2
        answer = 0
        while a >= 0:
            answer += factorial(a + b) // (factorial(a) * factorial(b))
            a -= 1
            b += 2
        return answer

n개의 계단을 2계단씩 a번, 1계단씩 b번 오른다고 하면 해당 케이스에 나올 수 있는 가짓수는 $(a+b)!/a!b!$이다. 즉, 중복 조합을 이용하여 풀이 하였다.

다른 풀이 - dp

class Solution:
    dp = defaultdict(int)

    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        if self.dp[n]:
            return self.dp[n]
        self.dp[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
        return self.dp[n]

n번째 계단에 오를 수 있는 가짓수는 n-1번째 계단에서 1개 오르거나 n-2번째 계단에서 2개 오르는 경우이다.

Reference

파이썬 알고리즘 인터뷰 87번