When to prefer memoization over tabulation

MediumProgramming & DSA~4m

A DP has a state space of $10^{7}$ possible states, but for a given input only about $500$ of them are actually reachable from the top-level query, and the dependency chains can be up to $10^{6}$ states deep. Both top-down memoization and bottom-up tabulation give the same $O(\text{states})$ big-O in the worst case. Which single statement correctly identifies the right approach for this input and why?

Show hints (2)+

Only $\sim\!500$ of $10^7$ states are reachable - which method skips the rest?
But $10^6$ -deep recursion threatens the call stack - a fixable caveat, not a reason to switch.

Answer

Reveal answer →

Memoization - it computes only the $\sim\!500$ reachable states, but the $10^6$ -deep recursion must be made iterative or given a larger stack

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Options Trading

When to prefer memoization over tabulation

Answer

Related questions