[LeetCode] Climbing Stairs

문제 이동

어제 풀었던 피보나치 수열 문제랑 똑같은 풀이로 풀 수 있다!

첫 번째 제출 : 타뷸레이션

상향식 풀이 -> 재귀 X

class Solution:
    from collections import defaultdict
    dp  = defaultdict(int)
    def climbStairs(self, n: int) -> int:
        self.dp[1] = 1
        self.dp[2] = 2
        for i in range(3, n+1):
            self.dp[i] = self.dp[i-1] + self.dp[i-2]
        return self.dp[n]

두 번째 제출 : 메모이제이션

재귀

class Solution:
    # 타뷸레이션? 상향식 풀이
    from collections import defaultdict
    dp  = defaultdict(int)
    def climbStairs(self, n: int) -> int:
        if n < 3:
            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]

defaltdict 호출할 때 default 값 type을 빼먹지 말라.
defaultdict(int)

세 번째 제출 : 두 변수

class Solution:
    # 타뷸레이션? 상향식 풀이
    def climbStairs(self, n: int) -> int:
        x, y = 1, 2
        for _ in range(n-1):
            x, y = y, x + y
        return x