 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.