#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/climbing-stairs-memoized-solution

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/climbing-stairs-memoized-solution

Repovive

LeetCode 70 Climbing Stairs - Memoized Solution - Dynamic Programming Fundamentals | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 70 Climbing Stairs - Memoized Solution

Apply the pattern

Now apply the memoization pattern to climbing stairs:

function climbStairs(n, dp)
    if dp[n] ≠ -1 then
        return dp[n]
    if n = 1 then
        return 1
    if n = 2 then
        return 2
    dp[n] := climbStairs(n - 1, dp) + climbStairs(n - 2, dp)
    return dp[n]

The structure is identical to memoized Fibonacci, just with adjusted base cases. This runs in $O(n)$ time and $O(n)$ space.

You've now applied the same memoization pattern to two different problems. Learn once, use everywhere. That's why patterns matter. Take time to work through examples. The pattern becomes clearer with practice. Compare the runtime to the naive version. The difference is dramatic even for small inputs.