LeetCode Entry

70. Climbing Stairs

12.12.2022 easy 2022 kotlin

val cache = mutableMapOf()

70. Climbing Stairs easy

https://t.me/leetcode_daily_unstoppable/49

blog post

    val cache = mutableMapOf<Int, Int>()
    fun climbStairs(n: Int): Int = when {
        n < 1  -> 0
        n == 1 -> 1
        n == 2 -> 2
        else -> cache.getOrPut(n) {
            climbStairs(n-1) + climbStairs(n-2)
        }
    }

You can observe that result is only depend on input n. And also that result(n) = result(n-1) + result(n-2). Just use memoization for storing already solved inputs.

Space: O(N), Time: O(N)