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.
For a connected, weighted, undirected graph, grow a tree from any root . For every vertex outside the tree, store the cheapest edge currently connecting it to the tree, not its source-path distance:
for v in V: key[v] = infinity; parent[v] = none
key[r] = 0
Q = indexed min-priority-queue containing all vertices
while Q is not empty:
u = extract-min(Q)
if parent[u] != none: output edge (parent[u],u)
for each edge {u,v} of weight w with v still in Q:
if w < key[v]:
key[v] = w
parent[v] = u
decrease-key(Q,v,w)The maintained key chooses the minimum-weight edge crossing the cut between the tree and remaining vertices. The minimum spanning tree cut property makes that edge safe; induction therefore preserves the existence of a minimum spanning tree containing all selected edges. This proves why Prim's algorithm is greedy and correct. With adjacency lists and a binary heap its time is . For a disconnected graph, starting another component when the minimum key is infinity produces a minimum spanning forest instead of claiming that a spanning tree exists.
Let be the best sum of a segment ending at position , allowing the empty segment with sum zero. The maximum subarray problem recurrence isAn optimal nonempty segment ending at extends the best suffix ending at , or starts fresh; a negative suffix cannot help. Keep its start index and record endpoints whenever a new overall best is found:
suffix = 0; best = 0
start = 0; bestLeft = 0; bestRight = 0
for i = 0,...,n-1:
suffix = suffix + A[i]
if suffix < 0:
suffix = 0; start = i+1
if suffix > best:
best = suffix
bestLeft = start; bestRight = i+1
return A[bestLeft:bestRight]The half-open endpoint interval is empty initially, so empty input and all-negative input correctly return an empty segment. The invariant identifies the best nonnegative suffix and the best segment in the scanned prefix, proving correctness. This is Kadane's algorithm, using time and auxiliary space, excluding the returned slice. The displayed example yields sum , from the segment .
Articles by others on the same topic
There are currently no matching articles.