Greedy vs Dynamic Programming

Both build an answer from smaller pieces. Greedy commits to one choice and moves on. DP keeps every choice open and picks the best at the end. That single difference decides which one is correct.

Side by side

• Greedy - one path through the choices. Usually O(n log n) for the sort. No extra memory.
• DP - every path, with repeats cached. Usually O(n × m). Needs a table or a cache.
• Greedy is correct only when the local best is provably part of the global best.
• DP is correct whenever the problem has optimal substructure, which is a much weaker requirement.

The same problem, both ways

"Maximum value you can carry within a weight limit." With whole items, greedy fails and DP is needed. Allow fractions of items and greedy becomes correct.