Practice question · Multiple choice
Memoisation and tabulation both solve the same dynamic programming problems. When does the choice actually matter?
Hints
- Ask which approach computes a subproblem that no path ever needs.
- Consider a huge state space where only a thin slice is reachable from the input.
Show the answer
B. When only part of the state space is ever reached
Why
Tabulation fills everything; memoisation computes only what the recursion reaches. On a sparse state space that is the whole difference, and it runs the other way too, since tabulation avoids call overhead and stack depth. Neither dominates, which is why both are taught.
Practise Dynamic Programming Intuition
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Dynamic Programming Intuition
- Match each dynamic programming concept to its meaning.
- Select every problem the lesson names as a classic dynamic programming problem.
- Sort each description by which style of dynamic programming it belongs to.
- Naive recursive Fibonacci takes exponential time; adding memoisation makes it linear. Why does storing…