[Leetcode] 70. climbing stairs

문제

https://leetcode.com/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-100-liked

풀이

top down 풀이와 bottom up풀이가 모두 가능하고, 메모이제이션을 통해 반복되는 연산을 하지 않도록 했습니다.

결론적으로 이 문제는 피보나치 수를 구하는 것과 동일합니다.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)  # dp[n]: n steps에 가능한 distinct ways 수
        dp[0] = 1
        dp[1] = 1

        for i in range(2, n + 1):  # 2 ~ n
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

discussion을 보니 dp로 저장하는 자료구조를 hash map(python의 dictionary)으로 이용하는 경우도 있었습니다.

공간복잡도를 O(N)이 아닌 O(1)로 하기 위해 다음과 같은 풀이도 가능합니다.

def climbStairs(self, n):
    a = b = 1
    for _ in range(n):
        a, b = b, a + b
    return a