Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 6 / a / Solution

Dynamic programming defines subproblem optima and combines their stored answers through a recurrence. It is useful when optimal substructure and overlapping subproblems allow repeated work to be shared. Several alternative choices can be compared before an optimum is selected.

A greedy algorithm instead commits to a locally selected choice and does not later reconsider it. To be correct, its choice needs a justification such as an exchange argument or a safe-cut property, beyond merely having optimal substructure. Neither method is automatically applicable to every optimization problem. Prim's algorithm illustrates a justified greedy choice; the maximum-segment recurrence below illustrates dynamic programming.