7.2 Dynamic Programming

Question 1

Differences between divide & conquer and dynamic programming?

Answer 1

Divide & Conquer:
Top-Down
Recursively divides the input into disjoint subinstances
Often for decision of computation problems

Dynamic Programming:
Bottom-Up
Divides the instance into overlapping subinstances
Solutions to subinstances are stored, not recomputed
Often for optimisation problems