[LeetCode] 70 | Climbing Stairs | Python

---

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

---

문제

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

---

조건

• 1 <= n <= 45

---

내 풀이

Dynamic Programming으로 푸는, 유명한 문제 중 하나다.

n번째 계단으로 가는 방법은, n-1번째 계단에서 한 칸 올라가는 방법과 n-2번째 계단에서 두 칸 올라가는 방법이 있다.

따라서 n번째 계단으로 가는 방법은 n-1번째 계단까지 가는 방법 + n-2번째 계단까지 가는 방법이 된다. (dp[n] = dp[n-1] + dp[n-2])

---

코드

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [1, 1]
        for step in range(2, n+1):
            dp.append(dp[step-2] + dp[step-1])
        
        return dp[n]