[LeetCode] 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?

 

예시

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

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

---

풀기

해석하면 n이라는 숫자가 있는데 1 또는 2를 더해서 만들 수 있는 경우의 수 구하라는 문제이다.

대표적인 DP 문제라고 한다. (gpt 왈)

 

일단 DP로 분류되어 있던 문제이니 규칙을 찾아보려고 했었다.

n	경우	output
1	(1)	1
2	(1, 1), (2)	2
3	(2, 1), (1, 2), (1, 1, 1)	3
4	(2, 2), (2, 1, 1), (1, 2, 1), (2, 1, 1), (1, 1, 1, 1)	5
5	(2, 2, 1), (2, 1, 2), (1, 2, 2), (2, 1, 1, 1), (1, 2, 1, 1), (1, 1, 2, 1), (1, 1, 1, 2), (1, 1, 1, 1, 1)	8
...	...	...

 

n이 5일때까지 확인해보면 위 표와 같다.

output의 값을 보면 점화식은 다음과 같다는 걸 알 수 있다.

dp[n] = dp[n - 1] + dp[n - 2]

 

자 그럼 코딩 ㄱㄱ

---

결과

class Solution {
    fun climbStairs(n: Int): Int {
        return when (n <= 2) {
            true -> n
            false -> {
                val dp = IntArray(n + 1)

                dp[1] = 1
                dp[2] = 2

                for (i in 3 .. n) {
                    dp[i] = dp[i - 1] + dp[i - 2]
                }

                dp[n]
            }
        }
    }
}