Practice question · Sort into groups
Sort each description by which style of dynamic programming it belongs to.
Groups: Memoization (top-down) · Tabulation (bottom-up)
- Fill a table from the smallest subproblem upward
- Ensure each entry is ready before larger ones need it
- Return a stored value on later calls
- Write the natural recursion and cache results as computed
Hints
- Top-down starts from the original problem and recurses, caching along the way.
- Bottom-up starts from the base cases and builds upward.
Show the answer
Memoization (top-down): Write the natural recursion and cache results as computed, Return a stored value on later calls
Tabulation (bottom-up): Fill a table from the smallest subproblem upward, Ensure each entry is ready before larger ones need it
Why
Memoization keeps the natural recursion but caches; tabulation abandons recursion and fills a table from the base cases up. Both compute the same answers, just in opposite directions.
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.
- Memoisation and tabulation both solve the same dynamic programming problems. When does the choice actually…
- Select every problem the lesson names as a classic dynamic programming problem.
- Naive recursive Fibonacci takes exponential time; adding memoisation makes it linear. Why does storing…