= Solution
Both <divide-and-conquer algorithms> and <dynamic programming> derive answers from smaller problems. A typical <divide-and-conquer algorithm>, such as <merge sort>, splits an instance into separate parts and combines their answers. <Dynamic programming> additionally identifies repeated states across different decompositions and reuses their answers; <matrix-chain multiplication> is a standard example.
Thus a recursion tree may repeatedly solve the same state, whereas a <dynamic programming> table or <memoization> stores it once. The resulting recurrence and dependency order determine the <running time>. The <principle of optimality> supports combining optimal state answers; it does not by itself justify a <greedy algorithm>.
Back to article page
