= 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.
Back to article page
