📃 문제 설명

Climbing Staris

[문제 출처 : LeetCode]

👨‍💻 해결 방법

DP문제이다.

1개의 계단을 오르는 방법은 한가지, f(1) = 1
2개의 계단을 오르는 방법은 두가지, f(2) = 2

3개의 계단을 오르는 방법은,
처음에 1개의 계단을 오르고 2개의 계단을 오르는 것과
처음에 2개의 계단을 오르고 1개의 계단을 오르는 경우의 수를 합하면 되기 때문에, f(3) = f(2) + f(1) = 3
...
결국 f(n) = f(n-1) + f(n-2)를 이용하여 DP로 풀면 된당.
(재귀로도 풀 수 있지만 계산량이 너무 많음.. 거의 피보나치 수열 문제)
memorization을 위해 cache라는 딕셔너리를 사용했다.

👨‍💻 소스 코드

class Solution:
    cache = {}

    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        else:
            return self._climbStairs(n - 1) + self._climbStairs(n - 2)

    def _climbStairs(self, n: int):
        if n not in self.cache:
            self.cache[n] = self.climbStairs(n)
        return self.cache[n]