Memoisation

Memoisation is the top-down form of dynamic programming. You still write the recursive function. Before you recurse, you look in a table to see whether this exact state was already solved. If it was, you return the stored answer. If it was not, you compute it, store it, and then return it.

The table is often a plain object from the state to the answer. For the stairs, the state is how many steps are left. The keys have to be the whole state that the answer depends on. If two calls are the same subproblem and you only keyed part of it, you will reuse an answer that belonged to a different call.

The space is the point. You are spending memory so that overlapping calls do not do the work again. A bottom-up loop fills the same ideas in an order that makes the lookup feel unnecessary, because the smaller answers are already sitting there when you need them. When you trust that order, the loop is shorter. Until you do, the cache on the recursive function is a correct way to see the overlap.