[leetcode] 70. Climbing Stairs - Python

🔍 Problem

https://leetcode.com/problems/climbing-stairs/

---

📰 문제풀이

• 제한 시간: 15분
• 성공 여부: 성공

---

📃 Solving Process

1. 다이나믹 프로그래밍 문제로 주어진 문제의 패턴을 확인하면 된다. 이 부분은 글보다는 그림으로 보여주는 게 더욱 좋을 거 같아 다음 그림을 첨부한다.
   
2. 이와 같은 관계가 있기 때문에, 현재 자신의 숫자를 만들 수 있는 경우의 수는 dp[i] = dp[i - 1] + dp[i - 2]로 계산할 수 있다.

---

💻 Code

# 초기 답안
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        dp = [0] * n
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]

# 개선 답안
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        dp = [0] * n
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]
 

---

⏱ Time Complexity

• 총 N만큼 탐색하므로 $O(N)$이다.

---

💾 Space Complexity

• 공간 복잡도 역시 N만큼의 배열이 필요하므로 $O(N)$이다.