70. Climbing Stairs

Climbing Stairs - LeetCode

1. Dynamic Programming

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [[0] * 2 for _ in range(46)]
        dp[1][0] = 1
        dp[2][0] = 1
        dp[2][1] = 1
        for i in range(3, n + 1):
            dp[i][0] = sum(dp[i - 1])
            dp[i][1] = sum(dp[i - 2])
        return sum(dp[n])

DP 문제는 쉽던 어렵던 풀면 뭔가 기분이 좋다.

참고로 BFS로 접근하려다가 뭔가 알 수 없는 위기를 느껴서 DP로 전환했다.

 

2. Fibonacci Number (?..._)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        first, second = 1, 2
        for i in range(3, n + 1):
            third = first + second
            first = second
            second = third
        return second

그렇다. 이 문제는 피보나치수열을 구하라는 문제와 똑같은 문제였다.

 

그 외에도 굉장히 다양한 풀이법이 있었는데 직접 코드를 짠 건 요기까지...