Greedy vs Dynamic Programming: How to Tell Which One a Problem Needs

You should always try a greedy choice first because it requires zero extra memory and runs in O(n) or O(n log n) time, but you must switch to dynamic programming the moment a local optimal choice ruins your global result.

The Trap of Local Choices

During an online assessment, you will often stare at an array of numbers and wonder if sorting it will solve everything. Greedy algorithms rely on making the best possible decision at the current step without looking ahead. If you are given coin denominations of [1, 5, 6, 8] and need to make a target of 11, a greedy approach picks the largest coin under 11 first, which is 8. That leaves a remainder of 3. Your next coin is 1, and your final coin is 1 for a total of three coins: 8 + 1 + 1.

The Counterexample That Breaks Greedy

That same coin change problem exposes the fatal flaw of greedy choices. The optimal way to make 11 with coins [1, 5, 6, 8] is actually 5 + 6, which uses only two coins. Your greedy choice of 8 locked you into a suboptimal branch because you committed to a decision before seeing the full combination space. When a problem exhibits overlapping subproblems and optimal substructure where a local decision alters future possibilities, greedy fails and dynamic programming is mandatory.

The Exchange Argument

Proving a greedy algorithm works requires an exchange argument. Assume an optimal solution exists that differs from your greedy solution at the first step. You then show that swapping the first element of that optimal solution with your greedy choice does not worsen the total objective function value. Take Activity Selection where you receive intervals like (1, 3), (2, 5), and (4, 7). Sorting by finish time and picking (1, 3) leaves the maximum possible timeline open for the remaining n - 2 intervals. If you swapped (1, 3) for (2, 5), you would finish later and squeeze out subsequent valid events.

When Greedy Is Provably Right

Some structures guarantee that local choices lead straight to the global optimum. Consider Jump Game where your input array is [2, 3, 1, 1, 4]. You track the maxReach index at every step using a simple for loop. If your current index exceeds maxReach, you return false. Otherwise, you update maxReach = max(maxReach, i + nums[i]). You never need to store past states in a dp table because the furthest reachable index completely summarizes all necessary history for the rest of the array.

The Rule for Your Next Mock Test

Check two things before writing code. Does the problem ask for a maximum or minimum value where future choices depend entirely on past subsets, like Knapsack or Edit Distance? Use dynamic programming and build a dp table. Does the problem allow sorting the input such that a single pass makes an irrevocable local choice that leaves the largest possible remaining domain, like Interval Scheduling or Huffman Coding? Write the greedy solution.

Open DSA Tracker and sort problems by tag to test this exchange logic on ten greedy and ten dynamic programming questions today.

Keep going with practice problems and the online compiler.

Further reading: Binary search trees on Wikipedia.