LeetCode 70 Climbing Stairs - Memoized Solution

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. Compare the runtime to the naive version. The difference is dramatic even for small inputs.