Practice question · Match the pairs
Match each dynamic programming concept to its meaning.
- Memoization
- Tabulation
- Overlapping subproblems
- Optimal substructure
- The same subproblem is needed many times
- Bottom-up filling of a table of subproblem answers
- Top-down recursion that caches each result
- An optimal solution built from optimal subsolutions
Hints
- Two entries are the two DP styles; two are the two features a DP problem needs.
- Memoization is top-down; tabulation is bottom-up.
Show the answer
- Memoization → Top-down recursion that caches each result
- Tabulation → Bottom-up filling of a table of subproblem answers
- Overlapping subproblems → The same subproblem is needed many times
- Optimal substructure → An optimal solution built from optimal subsolutions
Why
Memoization and tabulation are the two DP styles (top-down caching versus bottom-up table filling); overlapping subproblems and optimal substructure are the two properties that make DP applicable.
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
- 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.
- 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…