[LeetCode] 70. Climbing Stairs - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

유형 : 동적 계획법(Dynamic Programming)

문제 설명

한번에 계단을 1칸 혹은 2칸을 오룰 수 있을 때, 정수 n이 주어지면 n번째 계단에 오를 수 있는 방법의 개수를 return 하는 문제이다.

Example 1)
Input: n = 2
Output: 2

Example 2)
Input: n = 3
Output: 3

제한사항

• 1 <= n <= 45

문제 풀이

Recursive한 방법으로 생각해보자. 해당 문제에서 n번째 계단에 오를 수 있는 방법은 ① n-1번째 계단에서 오르는 방법, ② n-2번째 계단에서 오르는 방법으로, 총 두 가지이다. 따라서 n번째 계단에 오를 수 있는 경우의 수는 n-1번째 계단에 오를 수 있는 경우의 수에 n-2번째 계단에 오를 수 있는 경우의 수를 더한 값이다. 이를 점화식으로 나타내면 아래와 같고, 가장 작은 문제의 상태를 나타내는 기저 상태는 1번째 계단에 오르는 경우와 2번째 계단에 오르는 경우로 각각 1, 2라는 해를 가진다. 점화식과 기저 상태를 알면 Top-Down 방식이나 Bottom-Up 방식으로 코드를 작성할 수 있다.

성공 코드

from typing import List

class Solution:
    def climbStairs(self, n: int) -> int:
        dp_array = [0,1,2]

        if n < len(dp_array):
            return dp_array[n]

        for i in range(3, n+1):
            ith_way = dp_array[i-1] + dp_array[i-2]
            dp_array.append(ith_way)

        return dp_array[n]

시간 복잡도 : O(n)

공간 복잡도 : O(n)