Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 6 / b / 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.