Greedy versus dynamic programming

Coin change worked both ways, showing exactly where greedy breaks and DP does not.

14 min read · Lesson 6 of 6 · Pro

Two ways to make a sequence of choices

Many problems are a chain of decisions. Two strategies:

Greedy: at each step take what looks best right now, never reconsider.

Fast, short, and sometimes wrong.

Dynamic programming: work out the best answer for every smaller

subproblem, store it, and build up. Slower, always right when the problem fits.

The skill being tested is knowing which applies. Greedy is not "the easy one" - it is the one that needs a proof.

Worked example 1: activity selection, where greedy is correct

You have n events with start and finish times. Attend the maximum number that do not overlap. This is the classic hall-scheduling problem.

The rest of this lesson is Pro

The free lessons of Algorithms and Complexity finish what they start — read those first if you have not. This one goes further, and it is part of the paid half.

A pass opens the paid lessons of every course, the mock test papers and the company-wise series. It ends on its own date; nothing renews by itself.

Get a pass — from ₹29 for 7 days

Already bought one? Log in.