Memoization vs Tabulation in Dynamic Programming

Memoization and tabulation are two ways to implement the same dynamic programming idea, and they have the same time complexity, so neither is more real DP than the other; they just differ in direction and tradeoffs. Memoization is top-down. I write the natural recursive solution straight from the recurrence, and I add a cache, an array or a map, where I store each subproblem's result the first time I compute it. Before doing any work, I check the cache, so each subproblem is solved only once. The big advantages are that it's easy to write because it mirrors the recurrence, and it only ever computes the subproblems that are actually reachable, which helps when the state space is sparse. Tabulation is bottom-up. Instead of recursion, I figure out an order in which to fill a table, starting from the base cases and building up to the final answer iteratively. Its advantages are that there's no recursion, so no function-call overhead and no risk of a stack overflow on very deep inputs, and it often makes space optimization easy. For example, Fibonacci tabulated only needs the last two values, so I can drop the whole array down to constant space with a rolling pair of variables. So my practical strategy in an interview is: derive the recurrence, implement it with memoization first because it's quick and clear, and then, if I'm worried about stack depth or I need to reduce the space, convert it to a bottom-up tabulation, possibly with a rolling array.