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.
Articles by others on the same topic
There are currently no matching articles.