70.climbing-stairs.md

70. Climbing Stairs

Top-Down DP

fun climbStairs(n: Int): Int {
    val memo = IntArray(n + 1) { -1 }
    return topDown(n, memo)
}

private fun topDown(n: Int, memo: IntArray): Int {
    if (n <= 2) return n
    if (memo[n] != -1) return memo[n]
    memo[n] = topDown(n - 1, memo) + topDown(n - 2, memo)
    return memo[n]
}

• Time Complexity: O(n) for each n in topDown function.
• Space Complexity: O(n) for memo array.

Bottom-Up DP

fun climbStairs(n: Int): Int {
    if (n <= 2) return n
    val dp = IntArray(n + 1)
    dp[1] = 1
    dp[2] = 2
    for (i in 3..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

• Time Complexity: O(n) for one for-loop.
• Space Complexity: O(n) for dp array.

Without Extra Space

fun climbStairs(n: Int): Int {
    if (n <= 2) return n
    var previous = 1
    var current = 2
    var result = 0
    for (i in 3..n) {
        result = previous + current
        previous = current
        current = result
    }
    return result
}

• Time Complexity: O(n) for one for-loop.
• Space Complexity: O(1).