Algorithms and Data Structures · Middle · Question 40 of 75
Which two properties make a problem a good fit for dynamic programming?
- 1Sorted input and a single unique answer
- ✓Correct answer: Overlapping subproblems and optimal substructure
- 3A graph structure with positive edge weights
Explanation
Overlapping subproblems means the same sub-results are needed many times, so caching them pays off. Optimal substructure means the best answer is built from best answers to subproblems.