Skip to content

LC 070. Climbing Stairs

mccornet edited this page Jul 28, 2021 · 5 revisions

Leetcode 70. Climbing stairs

Note that while this is a recursive problem, and in these examples solved that way: the answer actually is the Fibonacci series and can be solved a lot more efficiently.

Recursive

Python

from functools import lru_cache

class Solution:
    
    # Solution 1
    @lru_cache
    def climbStairs(self, n: int) -> int:
        # if we reach the top we return 1
        if n == 0: return 1
        if n < 0: return 0 # this was illegal 
        
        # not at the top?
        count = self.climbStairs(n-1) + self.climbStairs(n-2)
        
        return count

Bottom-up

Note that in this code we compute the whole table, just like in Leetcode 322. Coin Change, but we only ever use the last two values. However, this method would be more adaptable to adding different number of steps. And can be found on project-euler.com as something like: number of ways to make change.

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    
    let dp_cache = new Array(n+2);
    // base cases
    dp_cache[0] = 0;
    dp_cache[1] = 1;
    
    for(let i = 2; i <= n+1; i++) 
    {
        dp_cache[i] = dp_cache[i-1] + dp_cache[i-2]
    }

    return dp_cache[n+1];
};

Clone this wiki locally