(LeetCode) 70. Climbing Stairs

70. Climbing Stairs

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Dynamic Programming
• 난이도 : Easy

Problem

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

Solution (Recursive)

Exapnder

class Solution {
    fun climbStairs(n: Int): Int = if (n <= 2) {
        n
    } else {
        climbStairs(n - 1) + climbStairs(n - 2)
    }
}

Solution (Memoization)

Exapnder

class Solution {
    fun climbStairs(n: Int): Int {
        var dp = IntArray(n + 1) { 0 }
        dp.forEachIndexed { i, v ->
            when (i) {
                0 -> dp[i] = 0
                1 -> dp[i] = 1
                2 -> dp[i] = 2
                else -> dp[i] = dp[i - 1] + dp[i - 2]
            }
        }
        return dp[n]
    }
}

Point of Thinking

• 아무 생각없이 재귀로 돌렸다가 Testcase 41에서 time out을 맞았다.
• 메모이제이션 적용 후 Accepted.
• 매우 기초지만 정석적인 DP문제다. 한국의 퐁당퐁당 문제급.