= 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.
Back to article page
