Climbing Stairs

TARGET DECK: Leetcode FILE TAGS:

Intuition

• For top down, for each step, you have two options: Jump to the next step or next next step.
  • If you overshoot (i.e. are past the nth step), then ignore this.
  • Otherwise, once you have reached the nth step, backtrack for all the ways you reached that step.
  • Then, memoize this solution, storing the computation of the subproblems in a DP array.
• For bottom up, set the 0th index to 1, which conceptually means there is 1 way to reach the 0th index (credit BrainlessSociety).
  • It is similar to adding + 1 for one new way to get to the top by going another step.

Cards

START Basic Front: Climbing Stairs - LeetCode Back: Set the 0th index to 1 when doing bottom up.

END

Complexity

Runtime

• $O(2^N)$ without memoization since on each index, you are making the choice whether to go to the next step, or the next next step.
• $O(N)$ with memoization since you are only going up the staircase once.

Space

$O(1)$ with bottom up approach

Code

Bottom Up

class Solution:
    def climbStairs(self, n: int) -> int:
        prev = nxt = 1
        for _ in range(2, n + 1):
            prev, nxt = nxt, prev + nxt
        return nxt

Top Down

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [-1] * n
        def r(i):
            if i > n:
                return 0
            if i == n:
                return 1
 
            if dp[i] == -1:
                dp[i] = r(i + 1) + r(i + 2)
            return dp[i]
 
        return r(0)

Notes

---

References

Climbing Stairs - LeetCode