Python solution (linear time, and constant space) with dummies explanation

  • 1
    # linear time, and constant space complexity
    def climbStairs(self, n):
        if n < 3: return n
        n_minus_2_combos = 1
        n_minus_1_combos = 2
        for step in range(n-2):
            curr_combos = n_minus_1_combos + n_minus_2_combos
            n_minus_2_combos = n_minus_1_combos
            n_minus_1_combos = curr_combos
        return curr_combos

    Explanation: Not unlike the fibonacci algorithm, to efficiently gather the total combinations at n you need to sum up the last two (n-1 and n-2) combination counts. Using dynamic programming by storing these two last combinations at each iteration, the algorithm does not need to re-compute all past combinations.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.