Greedy Algorithms and Dynamic Programming

Many problems ask for the best solution among a huge number of candidates: the fewest coins, the most activities, the most valuable load. Trying every candidate is exponential. This chapter presents two design paradigms that avoid it: greedy algorithms, which commit to one locally best choice at each step and never look back, and dynamic programming (DP), which solves every subproblem once and combines the answers.

What makes an algorithm greedy

A greedy algorithm builds a solution piece by piece, always taking the choice that looks best now (the largest coin, the activity that ends first, the item with the best value per kilogram), and never undoes a choice. It is usually simple and fast, often just "sort, then one pass": O(n log n).

Greedy is correct only when the problem has two properties:

• Greedy choice property: some optimal solution starts with the greedy choice, so committing to it never loses.
• Optimal substructure: after the greedy choice, what remains is a smaller instance of the same problem, and an optimal solution to it completes an optimal solution to the whole.

The usual proof is an exchange argument: take any optimal solution, swap its first choice for the greedy one, and show the result is still valid and no worse.

When greedy fails: coin change

"Give change with the fewest coins: always take the largest coin that fits." With coins {1, 5, 10, 25} this is optimal. For 63: 25, 25 (13 left), 10 (3 left), 1, 1, 1 — six coins, and no solution uses fewer.

With coins {1, 3, 4} and amount 6:

Step	Amount left	Greedy takes	Why
1	6	4	largest coin ≤ 6
2	2	1	4 and 3 are too big
3	1	1
—	0	total 3 coins

Method	Coins	Count
greedy (largest first)	4 + 1 + 1	3
optimal	3 + 3	2

Taking the 4 looked best but prevented the better solution. Whether greedy works depends on the coin system, so for arbitrary coins you need dynamic programming (below).

Activity (interval) scheduling

Given activities with start and finish times, choose the largest number of non-overlapping ones (an activity may start exactly when the previous one finishes).

Greedy rule: sort by finish time, then take every activity that starts at or after the finish of the last one taken.

// acts[i] = {start, finish}
Arrays.sort(acts, (x, y) -> Integer.compare(x[1], y[1]));
int count = 0, lastFinish = Integer.MIN_VALUE;
for (int[] act : acts) {
    if (act[0] >= lastFinish) {
        count++;
        lastFinish = act[1];
    }
}

Worked example with eight activities, already sorted by finish time:

time 0  1  2  3  4  5  6  7  8  9  10 11
A       [========)
B             [=====)
C    [=================)
D                   [=====)
E             [=================)
F                   [===========)
G                      [===========)
H                            [========)

Activity	[start, finish)	start ≥ lastFinish?	Decision	lastFinish after
A	[1, 4)	1 ≥ −∞	take	4
B	[3, 5)	3 < 4	skip	4
C	[0, 6)	0 < 4	skip	4
D	[5, 7)	5 ≥ 4	take	7
E	[3, 9)	3 < 7	skip	7
F	[5, 9)	5 < 7	skip	7
G	[6, 10)	6 < 7	skip	7
H	[8, 11)	8 ≥ 7	take	11

Result: A, D, H — 3 activities. Trying all 256 subsets confirms that 3 is the maximum. (The rule "earliest start" would take C first, which blocks the room until 6, and ends with only C and G: 2 activities.)

Why it works: the activity that finishes first leaves the most room for the rest. If an optimal schedule starts with some other activity, replacing it by the earliest-finishing one keeps the schedule valid (it ends no later) and the count unchanged. Time: O(n log n) for the sort plus O(n).

Fractional knapsack

A knapsack holds weight W; item i has weight wᵢ and value vᵢ, and you may take any fraction of an item. Greedy by value per unit weight (vᵢ/wᵢ) is optimal: take the best-ratio items whole while they fit, then a fraction of the next one.

Example, W = 10, items (weight, value): (5, 30), (4, 28), (6, 24), (3, 9). Ratios 6, 7, 4, 3. Take (4, 28), then (5, 30): weight 9, value 58. One unit of capacity is left, so take 1/6 of (6, 24) for 4 more: 62.

Step	Item (w, v)	Ratio	Amount taken	Capacity left	Total value
1	(4, 28)	7	all	10 − 4 = 6	28
2	(5, 30)	6	all	6 − 5 = 1	58
3	(6, 24)	4	1/6	0	58 + 4 = 62
4	(3, 9)	3	nothing (bag full)	0	62

In the 0/1 knapsack (each item taken whole or not at all) the same greedy rule fails, and you need DP.

Huffman coding (idea)

To compress a text, give frequent characters short bit codes and rare ones long codes. The code must be prefix-free (no code is the beginning of another), so a bit string decodes in only one way.

Huffman's greedy algorithm: put every character in a priority queue by frequency; repeatedly remove the two least frequent trees, join them under a new node whose frequency is their sum, and put it back; stop when one tree remains. Left edges are 0, right edges are 1, and a character's code is its path from the root.

Example with frequencies A:1, B:2, C:3, D:4: join A+B (3), then that with C (6), then with D (10). Codes: D = 0, C = 10, A = 110, B = 111 (0/1 labels may be swapped). Total bits = 4·1 + 3·2 + 1·3 + 2·3 = 19, against 2·10 = 20 for a fixed 2-bit code. With a priority queue this runs in O(n log n) for n distinct characters.

Step by step — the priority queue after each join:

Step	Remove the two smallest	New node	Queue after the step
start			A:1, B:2, C:3, D:4
1	A:1, B:2	(AB):3	C:3, (AB):3, D:4
2	C:3, (AB):3	(C AB):6	D:4, (C AB):6
3	D:4, (C AB):6	root:10	root:10 — done

            (10)
          0/    \1
         D:4    (6)
              0/    \1
             C:3    (3)
                  0/    \1
                 A:1    B:2

Read each code from the root: D = 0, C = 10, A = 110, B = 111. No code starts with another code, so "110010" can only be read as 110 | 0 | 10 = A D C.

From recursion to dynamic programming

DP applies when a problem has:

• Optimal substructure: an optimal solution is built from optimal solutions to subproblems.
• Overlapping subproblems: the plain recursion solves the same subproblems again and again.

Divide-and-conquer (Chapter 7) splits into independent subproblems; DP is for when they overlap. Naive recursive Fibonacci computes fib(n - 2) both directly and inside fib(n - 1), and the repetition grows exponentially. DP stores each answer the first time it is computed.

See the repetition. The calls made by the plain recursive fib(5):

                         fib(5)
                  /                  \
             fib(4)                    fib(3)
           /        \                /        \
       fib(3)       fib(2)       fib(2)      fib(1)
      /     \       /    \       /    \
  fib(2)  fib(1) fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

15 calls, but only 6 different questions (fib(0) … fib(5)). fib(3) is computed twice and fib(2) three times. It gets much worse as n grows:

n	5	10	20	30
calls of plain fib(n)	15	177	21 891	2 692 537
calls with memoization				59

The recipe:

1. Define the state: what does dp[i] (or dp[i][j]) mean, in words?
2. Write the recurrence: how does a state follow from smaller states?
3. Base cases.
4. Order of evaluation: every state must be computed after the states it depends on.
5. Where the answer is, and how to reconstruct the solution if it is needed.

Top-down memoization vs bottom-up tabulation

You met memoization in Chapter 1: keep the recursion, but cache results in an array or HashMap. Tabulation removes the recursion and fills a table in order of increasing size.

static long[] memo = new long[100];      // 0 means "not computed yet"

static long fibMemo(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];    // already on a sticky note
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}

static long fibTab(int n) {
    if (n <= 1) return n;
    long[] dp = new long[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

The table filled cell by cell by fibTab(7):

i	0	1	2	3	4	5	6	7
dp[i]	0	1	0 + 1 = 1	1 + 1 = 2	1 + 2 = 3	2 + 3 = 5	3 + 5 = 8	5 + 8 = 13

Each cell looks only at the two cells to its left, which are already filled.

	Top-down (memoization)	Bottom-up (tabulation)
Form	recursive, plus a cache	loops over a table
Computes	only the states actually reached	every state in the table
Risk	deep recursion → StackOverflowError	must choose a correct fill order
Space tricks	hard	easy: keep only the rows you still need

Both have the same time complexity: (number of states) × (work per state). For Fibonacci, n states × O(1) = O(n), and since dp[i] only needs the previous two values, two variables give O(1) space.

Climbing stairs. If you may climb 1 or 2 steps at a time, the number of ways to reach step n is ways(n) = ways(n − 1) + ways(n − 2), ways(0) = ways(1) = 1: the last move was either a 1-step or a 2-step. It is Fibonacci again. With other allowed steps, sum over each allowed last step.

step n	0	1	2	3	4	5	6	7
ways(n)	1	1	2	3	5	8	13	21

Check ways(3) = 3 by listing: 1+1+1, 1+2, 2+1. ✓

Coin change: minimum coins and number of ways

Minimum coins. dp[x] = fewest coins that make amount x (∞ if impossible). The last coin used is some coin c ≤ x, so dp[x] = 1 + min over coins c ≤ x of dp[x − c], with dp[0] = 0.

For coins {1, 3, 4}:

x	0	1	2	3	4	5	6	7
dp[x]	0	1	2	1	1	2	2	2

dp[6] = 1 + min(dp[5], dp[3], dp[2]) = 1 + 1 = 2, which is 3 + 3, the answer greedy missed. Time O(amount × k) for k coin types, space O(amount).

How each cell was filled (try each coin as the last one):

x	last coin 1: 1 + dp[x − 1]	last coin 3: 1 + dp[x − 3]	last coin 4: 1 + dp[x − 4]	dp[x]
1	1 + 0 = 1	—	—	1
2	1 + 1 = 2	—	—	2
3	1 + 2 = 3	1 + 0 = 1	—	1
4	1 + 1 = 2	1 + 1 = 2	1 + 0 = 1	1
5	1 + 1 = 2	1 + 2 = 3	1 + 1 = 2	2
6	1 + 2 = 3	1 + 1 = 2	1 + 2 = 3	2
7	1 + 2 = 3	1 + 1 = 2	1 + 1 = 2	2

To get the coins, not just the count, remember which coin won in each cell: for 6 the winner is 3, leaving 3, whose winner is 3 again → 3 + 3.

Number of ways. ways[x] = number of ways to make x. To count combinations (3 + 1 and 1 + 3 are the same way), loop over coins on the outside:

long[] ways = new long[amount + 1];
ways[0] = 1;                              // one way to make 0: no coins
for (int c : coins)
    for (int x = c; x <= amount; x++)
        ways[x] += ways[x - c];

With coins {1, 2, 5} and amount 5 this gives 4 (5, 2+2+1, 2+1+1+1, 1+1+1+1+1).

The array after each coin (each row = "using only the coins so far"):

After coin	x = 0	1	2	3	4	5
start	1	0	0	0	0	0
1	1	1	1	1	1	1
2	1	1	2	2	3	3
5	1	1	2	2	3	4

With only 1s there is one way for every amount. Adding the 2: ways[4] = 1 + ways[2] = 1 + 2 = 3 (1+1+1+1, 2+1+1, 2+2). Adding the 5 changes only ways[5]: 3 + ways[0] = 4.

0/1 knapsack

n items with weights wᵢ and values vᵢ, capacity W; each item is taken whole or not at all. K[i][c] = best value using only the first i items with capacity c:

• K[0][c] = 0 and K[i][0] = 0;
• K[i][c] = K[i − 1][c] if wᵢ > c (item i does not fit);
• otherwise K[i][c] = max(K[i − 1][c], vᵢ + K[i − 1][c − wᵢ]) — skip item i, or take it and fill the rest optimally from the first i − 1 items.

Example: W = 7, items (weight, value) = (1, 1), (3, 4), (4, 5), (5, 7).

i \ c	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1 (1, 1)	0	1	1	1	1	1	1	1
2 (3, 4)	0	1	1	4	5	5	5	5
3 (4, 5)	0	1	1	4	5	6	6	9
4 (5, 7)	0	1	1	4	5	7	8	9

The answer is K[4][7] = 9 (items 2 and 3). Time and space Θ(nW). This is called pseudo-polynomial: W is a number in the input, written with only about log W digits, so the running time is exponential in the size of W.

How some cells are computed — each cell looks only at the row above:

Cell	Item	Skip it: K[i − 1][c]	Take it: v + K[i − 1][c − w]	Result
K[2][4]	(3, 4)	K[1][4] = 1	4 + K[1][1] = 4 + 1 = 5	5 (take)
K[3][5]	(4, 5)	K[2][5] = 5	5 + K[2][1] = 5 + 1 = 6	6 (take)
K[3][7]	(4, 5)	K[2][7] = 5	5 + K[2][3] = 5 + 4 = 9	9 (take)
K[4][6]	(5, 7)	K[3][6] = 6	7 + K[3][1] = 7 + 1 = 8	8 (take)
K[4][7]	(5, 7)	K[3][7] = 9	7 + K[3][2] = 7 + 1 = 8	9 (skip)
K[4][3]	(5, 7)	K[3][3] = 4	does not fit (5 > 3)	4 (skip)

Longest common subsequence

A subsequence keeps characters in order but may skip some ("GRAM" is a subsequence of "PROGRAM"). The LCS of two strings x (length m) and y (length n) is the longest string that is a subsequence of both. dp[i][j] = LCS length of the prefixes x[0..i) and y[0..j):

• dp[i][0] = dp[0][j] = 0;
• if x[i − 1] == y[j − 1]: dp[i][j] = dp[i − 1][j − 1] + 1;
• else dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]).

int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        if (x.charAt(i - 1) == y.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

Small worked example: x = "ABCD" (rows), y = "ACBD" (columns). Fill row by row, left to right:

	""	A	C	B	D
""	0	0	0	0	0
A	0	1 ↖	1	1	1
B	0	1	1	2 ↖	2
C	0	1	2 ↖	2	2
D	0	1	2	2	3 ↖

• A = A at (1, 1): diagonal 0 + 1 = 1.
• B = B at (2, 3): diagonal dp[1][2] = 1, plus 1 = 2.
• C = C at (3, 2): diagonal dp[2][1] = 1, plus 1 = 2.
• D = D at (4, 4): diagonal dp[3][3] = 2, plus 1 = 3.
• Every other cell copies the larger of its upper and left neighbours.

The LCS length is 3. Two LCSs exist, "ABD" and "ACD"; the walk back below finds one of them.

Reconstruction. Start at (m, n). If the characters match, that character is in the LCS: record it and move diagonally to (i − 1, j − 1). Otherwise move to the neighbour holding the larger value, up (i − 1, j) or left (i, j − 1); on a tie, a fixed rule (for example "prefer up") makes the output deterministic. Stop at row or column 0 and reverse the recorded characters. For "PROGRAM" and "GRAMMAR" the length is 4 and one LCS is "GRAM".

For the small example with "prefer up": (4, 4) D = D → record D, go to (3, 3); C ≠ B, up = 2 ≥ left = 2 → go up to (2, 3); B = B → record B, go to (1, 2); A ≠ C, up = 0 < left = 1 → go left to (1, 1); A = A → record A. Reversed: "ABD".

Time Θ(mn), space Θ(mn); the length alone needs only two rows, Θ(min(m, n)) space, but then the path for reconstruction is lost.

Longest increasing subsequence

dp[i] = length of the longest strictly increasing subsequence that ends at a[i]. Every such subsequence is a[i] alone or extends one ending at some earlier, smaller a[j]:

dp[i] = 1 + max{ dp[j] : j < i and a[j] < a[i] } (or 1 if there is no such j). The answer is the maximum over all i, not dp[n − 1].

a	3	10	2	1	20	4	6	7
dp	1	2	1	1	3	2	3	4

The answer is 4 (for example 3, 4, 6, 7). Two nested loops: Θ(n²) time, Θ(n) space. (An O(n log n) method with binary search exists.) To reconstruct, also store prev[i], the j that gave the maximum, and follow the links back from the best i.

Cell by cell:

i	a[i]	Smaller earlier values (their dp)	dp[i]	prev[i]
0	3	none	1	—
1	10	3 (1)	2	0
2	2	none	1	—
3	1	none	1	—
4	20	3 (1), 10 (2), 2 (1), 1 (1)	3	1
5	4	3 (1), 2 (1), 1 (1)	2	0
6	6	3 (1), 2 (1), 1 (1), 4 (2)	3	5
7	7	3 (1), 2 (1), 1 (1), 4 (2), 6 (3)	4	6

Follow prev from i = 7: 7 → 6 (value 6) → 5 (value 4) → 0 (value 3). Reversed: 3, 4, 6, 7.

int[] dp = new int[n], prev = new int[n];
int best = 0;                                   // index where the longest chain ends
for (int i = 0; i < n; i++) {
    dp[i] = 1; prev[i] = -1;
    for (int j = 0; j < i; j++)
        if (a[j] < a[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; prev[i] = j; }
    if (dp[i] > dp[best]) best = i;
}

Reconstructing a solution

A DP table usually stores only values. To recover the choices, walk back from the answer cell and ask, at each cell, which case of the recurrence produced it:

• Knapsack: if K[i][c] ≠ K[i − 1][c], item i was taken; go to (i − 1, c − wᵢ). Otherwise go to (i − 1, c). In the table above: K[4][7] = K[3][7], so item 4 is skipped; K[3][7] = 9 ≠ K[2][7] = 5, so item 3 is taken, c = 3; K[2][3] = 4 ≠ K[1][3] = 1, so item 2 is taken, c = 0.
• Minimum coins: store which coin gave the minimum for each amount, then repeatedly subtract it.
• LCS / LIS: follow the matching diagonal steps or the prev links.

Reconstruction costs O(number of steps back), much less than filling the table.

Cost of a DP solution

Time = (number of states) × (time per state). Space = size of the table, often reducible when each row depends only on the previous one.

Problem	States	Per state	Time	Space
Fibonacci / stairs	n	O(1)	Θ(n)	Θ(1) with two variables
Minimum coins	amount	O(k)	Θ(amount·k)	Θ(amount)
0/1 knapsack	n·W	O(1)	Θ(nW)	Θ(nW), Θ(W) for the value only
LCS	m·n	O(1)	Θ(mn)	Θ(mn), Θ(min(m, n)) for the length only
LIS	n	O(n)	Θ(n²)	Θ(n)

Key takeaways

• Greedy = take the best-looking choice now and never undo it. Fast (often "sort + one pass"), but correct only with a proof (exchange argument); one counterexample shows it is wrong.
• Greedy works for activity scheduling (earliest finish), fractional knapsack (best value per weight) and Huffman coding (join the two least frequent). It fails for coins {1, 3, 4} and for 0/1 knapsack.
• DP needs optimal substructure and overlapping subproblems; D&C is for subproblems that do not repeat.
• Memoization = recursion + sticky notes (top-down); tabulation = fill a table from the smallest cases (bottom-up). Same time: states × work per state.
• Always define the state in words first: dp[x] = fewest coins for x; K[i][c] = best value with the first i items and capacity c; dp[i][j] = LCS of the first i and j characters; dp[i] = LIS ending at i.
• Counting coin combinations: coins in the outer loop; amounts outside gives ordered sequences.
• Reconstruct the answer by walking back from the final cell and asking which case produced each value.
• Know the costs: knapsack Θ(nW) (pseudo-polynomial), LCS Θ(mn), LIS Θ(n²), minimum coins Θ(amount · k).