Practice question · Select all that apply
Select every problem the lesson names as a classic dynamic programming problem.
Hints
- Four of these turn an exponential brute force into polynomial time by storing subresults.
- One of them is a divide-and-conquer sort, not a DP problem.
Show the answer
- A. Longest common subsequence
- B. Edit distance
- C. Shortest paths
- E. Knapsack
Why
Shortest paths, edit distance, knapsack, and longest common subsequence are the named DP problems. Merge sort is divide-and-conquer, its halves are independent, so there is nothing to reuse.
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…
- 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…