 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/functional-programming-design-and-analysis-of-algorithms/6/a/solution

There are three useful distinctions between dynamic programming and a conventional divide-and-conquer algorithm.

A divide-and-conquer algorithm typically splits one instance into mostly separate smaller instances; dynamic programming deliberately recognizes overlapping subproblems that recur along different decision histories.
A dynamic programming state is solved once and its result reused through a table or memoization. A direct divide-and-conquer algorithm normally combines the results of its recursive children without retaining a table indexed by all repeated states.
The dependency structure of a direct recursive decomposition is a recursion tree; dynamic programming evaluates a Directed acyclic graph of states in dependency order, either bottom-up or by memoization. Its cost is the number of distinct states times the work per state, rather than the number of occurrences in the expanded recursion tree.

These are paradigm-level distinctions, not mutually exclusive definitions: a recursive algorithm can use memoization, and dynamic programming need not be implemented iteratively. For optimization, the dynamic programming state and optimal substructure justify combining stored optimum values; storing repeated work alone does not prove the state is sufficient.

 New to topics? Read the docs here!