Staircase Problem — Recursion & Dynamic Programming

Same input, two ways: watch the recursive call tree, or watch the dp table fill in step by step.

Method

Input

Limits: without memoization, max 12 steps (753 recursive calls — more than that is unreadable). With memoization on, max 30 steps. Best for teaching: 4–8 steps.
Limits: dynamic programming handles up to 30 steps (a table of 31 cells). Best for teaching: 4–8 steps, then compare with recursion.

Playback

Speed

Same problem, three ways

Pseudocode

Ways found so far

none yet

Trace log

Ways found so far: 0
Currently at step 0 of 0
no run yet
not yet called
on the call stack
resolved (sum of children)
reached top (base case)
overstepped (base case)
cache hit (memoized)

Tabulation table (dp array)

cell being computedcells it reads fromtarget (the answer)