To yield an optimal solution, the problem should exhibit:
-
Optimal Substructure
An optimal solution to the problem contains within it optimal solutions to subproblems
-
Greedy Choice Property
Making locally optimal (greedy) choices leads to a globally optimal solution
How to Prove
