[Leetcode/파이썬] 70. Climbing Stairs

Climbing Stairs

---

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?

 

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

 

Constraints:

• 1 <= n <= 45

 

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 3 :
            return n

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

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

"""
1 : 1 : 1
2 : 11, 2 : 2
3 : 111, 12, 21 : 3
4 : 1111, 112, 121, 211, 22 : 5 
5 : 11111, 1112, 1121, 1211, 2111, 221, 212, 122 : 8 
6 : 111111, 11112, 11121, 11211, 12111, 21111, 1122, 1212, 1221, 2112, 2121, 2211, 222 : 13
"""

사실 이렇게 직접 다 찾아서 보니까 피보나치 식이 되어있었다. 

우선 예외사항부터 처리하자. n = 1, 2, 3 은 모두 n과 같은 값을 가지기 때문에 예외처리를 분명히 해준다. 

$$f(n) = n (n <= 3)$$

$$f(n) = f(n-1) + f(n-2) (n > 3)$$

이걸 잘 풀어서 작성하면 쉽게 문제해결 할 수 있다.