Skip to interview prep
Apexed

365. Compare top-down (memoised) and bottom-up (tabulated) dynamic programming.

MediumDynamic programming

Technical
Show model answer

Top-down follows the recurrence directly and only computes states that are actually reachable, which helps when the state space is sparse. Its costs are function-call overhead, hash-map lookups if states are not dense integers, and recursion depth (deep chains can overflow the stack in Python or JavaScript).

Bottom-up fills a table in an order where every dependency is already computed. It avoids recursion, is usually faster in practice, and makes space optimisation easy: if row i only reads row i − 1, keep two rows, which turns O(nW) knapsack space into O(W). The downside is that you must find a valid evaluation order and you may compute states that are never needed. Asymptotic time is the same for both.

Compare top-down (memoised) and bottom-up (tabulated) dynamic programming. — Data structures & algorithms interview question — Apexed