JAVA-205 · Lesson 11 of 12 · 19 min

Dynamic programming

▶ Video coming soon A video version of this lesson is on the way.

Two loose ends from earlier lessons meet on Tuesday, November 30, 2027, the last regular session of the term. Lesson 5's Fibonacci method made more than a million calls to compute 30 values, because it solved the same smaller problems again and again. And lesson 10's greedy method paid 6 hours of earn-a-bike credit with three vouchers when two would do. Both are fixed by dynamic programming: solve each smaller problem once, store its answer, and build bigger answers from the stored ones. Ingrid adds two shop problems to finish the evening: packing the trailer for the most valuable load, and spotting Kofi's typing mistakes in part codes.

Two ingredients

Dynamic programming, often shortened to DP, applies when a problem has two properties. It has optimal substructure: the best answer to the whole problem is built from best answers to smaller problems, the way the quickest route to Hilltop goes through the quickest route to the place before it. And it has overlapping subproblems: the same smaller problems come up again and again, so remembering their answers saves work. Divide and conquer has the first property but not the second; its pieces are independent. When pieces overlap, DP is the better tool.

Memoization: remember what you computed

The quickest fix for the Fibonacci method is to keep its recursive shape but store each answer the first time it is computed, and look it up after that. This is called memoization, from the idea of writing a memo to yourself. Each value from 1 to n is computed once, so the number of real computations drops from about 1.6ⁿ to n.

Java Example · Main.java
import java.util.*;

public class Main {
    static long calls = 0;
    static Map<Integer, Long> memo = new HashMap<>();

    static long fib(int n) {
        calls++;
        if (n <= 2) return 1;
        Long known = memo.get(n);
        if (known != null) return known;
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        for (int n : new int[] {30, 60, 90}) {
            calls = 0;
            memo.clear();
            System.out.println("fib(" + n + ") = " + fib(n) + " after " + calls + " calls");
        }
    }
}
Output
fib(30) = 832040 after 57 calls
fib(60) = 1548008755920 after 117 calls
fib(90) = 2880067194370816120 after 177 calls

What this code does

Before computing fib(n) the method checks the memo map, and after computing it, it stores the answer. Each value is then calculated once and every later request is a lookup, so fib(30) takes 57 calls instead of more than 1.6 million. fib(90) is still found instantly; without the memo it would need about 5.7 billion billion calls.

Tabulation: build from the bottom up

The other style of DP drops the recursion. Work out which smaller problems the answer depends on, solve them in order from the smallest up, and store their answers in an array, a table. For Fibonacci the table has n entries and each is the sum of the two before it. Tabulation uses no call stack, so it cannot overflow, and it often makes it easy to see how much memory is really needed: here only the last two values, so the table can shrink to two variables.

Java Example · Main.java
public class Main {
    public static void main(String[] args) {
        int n = 90;
        long[] table = new long[n + 1];
        table[1] = 1;
        table[2] = 1;
        for (int i = 3; i <= n; i++) table[i] = table[i - 1] + table[i - 2];
        System.out.println("table: fib(" + n + ") = " + table[n]);

        long a = 1, b = 1;
        for (int i = 3; i <= n; i++) { long c = a + b; a = b; b = c; }
        System.out.println("two variables: fib(" + n + ") = " + b);
    }
}
Output
table: fib(90) = 2880067194370816120
two variables: fib(90) = 2880067194370816120

What this code does

The table is filled from index 3 upwards, each entry the sum of the two before it, so every answer it needs is already there. The second loop keeps only the last two values, which is all the table was ever used for. Both take n steps and give the same answer.

Two ways to write dynamic programming
Memoization (top down)Tabulation (bottom up)
ShapeThe natural recursion plus a lookupA loop that fills a table in order
SolvesOnly the subproblems actually neededEvery subproblem up to the target
RiskDeep recursion can overflow the stackMust work out the right order to fill
Memory savingHardOften easy: keep only recent rows

Fewest vouchers, done properly

Lesson 10's voucher problem has optimal substructure. To pay h hours with the fewest vouchers, the last voucher used is worth 1, 3 or 4. Whichever it is, the rest must be the fewest vouchers for h − 1, h − 3 or h − 4. So best[h] = 1 + the smallest of best[h − 1], best[h − 3] and best[h − 4], ignoring any that would go below zero. Filling a table from 0 upwards gives the exact answer for every amount. The recurrence is the whole algorithm; the code just fills the table.

Java Example · Main.java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] vouchers = {1, 3, 4};
        int target = 10;
        int[] best = new int[target + 1];
        int[] last = new int[target + 1];
        for (int h = 1; h <= target; h++) {
            best[h] = Integer.MAX_VALUE;
            for (int v : vouchers) {
                if (v <= h && best[h - v] + 1 < best[h]) {
                    best[h] = best[h - v] + 1;
                    last[h] = v;
                }
            }
        }
        System.out.println("fewest vouchers for 0..10 hours: " + Arrays.toString(best));
        for (int h : new int[] {6, 10}) {
            List<Integer> used = new ArrayList<>();
            for (int x = h; x > 0; x -= last[x]) used.add(last[x]);
            System.out.println(h + " hours: " + used);
        }
    }
}
Output
fewest vouchers for 0..10 hours: [0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3]
6 hours: [3, 3]
10 hours: [3, 3, 4]

What this code does

best[h] is filled from 1 hour upwards by trying each voucher as the last one and adding one to the best answer for what remains. last records which voucher gave that best answer, so following it back rebuilds the actual vouchers. Six hours takes two 3-hour vouchers, which greedy missed, and ten hours takes three.

This table costs O(h × k) for h hours and k voucher values: a tiny amount of work, and it is always exact, whatever the values are. Recording a choice next to each table entry, like last here and parent in Dijkstra, is the standard way to recover the solution itself, not just its size.

Packing the trailer: the 0/1 knapsack

On collection days the trailer has room for 10 units of space. Kofi lists the donations waiting at a partner site, each with the space it takes and an estimate of what it will sell for after repair. Each item is either taken whole or left: this is the 0/1 knapsack problem. A greedy rule such as best value per unit of space first can fail, as the table in lesson 10 noted. Trying every subset of n items is O(2ⁿ). DP does it in O(n × capacity).

The table entry best[i][c] is the most value possible using only the first i items with c units of space. For item i there are two choices: leave it, giving best[i − 1][c], or, if it fits, take it, giving its value plus best[i − 1][c − its space]. The entry is the larger of the two. The answer is best[n][capacity].

Java Example · Main.java
import java.util.*;

public class Main {
    record Item(String name, int space, int value) {}

    public static void main(String[] args) {
        List<Item> items = List.of(new Item("kids bike", 2, 60), new Item("road bike", 4, 180),
                new Item("cargo frame", 5, 210), new Item("wheel set", 3, 90), new Item("box of tubes", 1, 40));
        int cap = 10, n = items.size();
        int[][] best = new int[n + 1][cap + 1];
        for (int i = 1; i <= n; i++) {
            Item it = items.get(i - 1);
            for (int c = 0; c <= cap; c++) {
                best[i][c] = best[i - 1][c];
                if (it.space() <= c) best[i][c] = Math.max(best[i][c], it.value() + best[i - 1][c - it.space()]);
            }
        }
        List<String> taken = new ArrayList<>();
        for (int i = n, c = cap; i > 0; i--) {
            if (best[i][c] != best[i - 1][c]) {
                taken.add(0, items.get(i - 1).name());
                c -= items.get(i - 1).space();
            }
        }
        System.out.println("best value " + best[n][cap] + ": " + taken);
        System.out.println("table cells filled: " + n * (cap + 1));
    }
}
Output
best value 430: [road bike, cargo frame, box of tubes]
table cells filled: 55

What this code does

Each row of the table adds one more item, and each cell keeps the better of leaving the item or taking it when it fits. Walking back from the last cell, an item was taken wherever its row changed the value, which rebuilds the chosen load. The best load is worth 430 and fills all 10 units, found by filling 55 cells instead of checking 32 subsets.

Greedy by value per unit of space would take the box of tubes (40 per unit), the road bike (45 per unit) and the cargo frame (42 per unit), worth 430, which happens to be optimal here. But change the trailer to 6 units: greedy takes the road bike and the box of tubes, worth 220, and nothing else fits in the 1 unit left, while DP finds the cargo frame and the tubes, worth 250. With a real n of a few dozen items and a capacity of a few hundred, DP is instant where trying every subset would take longer than the age of the universe.

Spotting typing mistakes: edit distance

Kofi types part codes fast, and the log has entries like CHIAN-11 and PAD-RAOD. To suggest the code he meant, StockRoom needs a measure of how different two strings are. The edit distance, or Levenshtein distance, is the fewest single-character insertions, deletions and substitutions that turn one string into the other. It has optimal substructure on prefixes: the distance between the first i characters of a and the first j of b depends only on the distances for shorter prefixes.

Java Example · Main.java
import java.util.*;

public class Main {
    static int distance(String a, String b) {
        int[][] d = new int[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++) d[i][0] = i;
        for (int j = 0; j <= b.length(); j++) d[0][j] = j;
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                int same = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
                d[i][j] = Math.min(Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1), d[i - 1][j - 1] + same);
            }
        }
        return d[a.length()][b.length()];
    }

    public static void main(String[] args) {
        List<String> codes = List.of("BELL", "CABLE-BRAKE", "CHAIN-11", "GRIPS", "PAD-DISC", "PAD-ROAD", "TUBE-700x25");
        for (String typed : List.of("CHIAN-11", "PAD-RAOD", "TUBE-700X25", "GRIP")) {
            String bestCode = null;
            int bestD = Integer.MAX_VALUE;
            for (String c : codes) {
                int dd = distance(typed, c);
                if (dd < bestD) { bestD = dd; bestCode = c; }
            }
            System.out.println(typed + " -> " + bestCode + " (distance " + bestD + ")");
        }
    }
}
Output
CHIAN-11 -> CHAIN-11 (distance 2)
PAD-RAOD -> PAD-ROAD (distance 2)
TUBE-700X25 -> TUBE-700x25 (distance 1)
GRIP -> GRIPS (distance 1)

What this code does

d[i][j] is the edit distance between the first i characters of one code and the first j of the other, built from three smaller cells: delete a character, insert one, or substitute when the characters differ. Each typed code is compared with every real code and the nearest is suggested. Swapped letters such as IA for AI cost two substitutions, and the capital X in TUBE-700X25 costs one.

A grid for the edit distance between CHIAN and CHAIN. The top row is the empty string then C, H, A, I, N; the left column is empty then C, H, I, A, N. The first row and column count up 0 to 5. Cells along the diagonal show 0, 0, then 1, 1 where I and A are swapped, ending in the bottom-right cell with 2. Arrows from three neighboring cells point into one cell, labeled delete, insert and substitute.
Each cell of the edit-distance table comes from the cell above, to the left or diagonally above-left

Comparing strings of lengths m and n fills an (m + 1) × (n + 1) table, so edit distance is O(m × n) for one pair. Spell checkers, DNA comparison tools and the diff program that shows changes between two files all use close relatives of this table. A related table finds the longest common subsequence of two strings, the longest sequence of characters that appears in both in the same order, which is this lesson's second exercise.

A method for DP problems

  • Define the subproblem in words: best[h] is the fewest vouchers for h hours; d[i][j] is the distance between two prefixes.
  • Write the recurrence: how a subproblem's answer comes from smaller ones, including the base cases.
  • Choose an order to fill the table so every answer a cell needs is already computed.
  • Read the final answer from the right cell, and keep a choice per cell if you need to rebuild the solution.
  • Check the cost: number of cells times work per cell, and see whether old rows can be discarded.

Try it yourself

Fewest stamps

The shop mails small parts using stamps worth 1, 5 and 6 units. Complete fewest(int[] values, int target) with a bottom-up table so it returns the fewest stamps that add up exactly to target.

The program should print 10 units: 2 stamps and 11 units: 2 stamps, then 12 units: 2 stamps.

public class Main {
    static int fewest(int[] values, int target) {
        int count = 0;
        for (int i = values.length - 1; i >= 0; i--) {
            while (target >= values[i]) { target -= values[i]; count++; }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] stamps = {1, 5, 6};
        for (int t : new int[] {10, 11, 12}) System.out.println(t + " units: " + fewest(stamps, t) + " stamps");
    }
}

Try it yourself

Longest common subsequence

Write lcs(String a, String b), which returns the length of the longest common subsequence: a table where L[i][j] is L[i-1][j-1] + 1 when the characters a[i-1] and b[j-1] match, and otherwise the larger of L[i-1][j] and L[i][j-1].

The program should print 4, 3 and 0, one per line.

public class Main {
    static int lcs(String a, String b) {
        int same = 0;
        for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
            if (a.charAt(i) == b.charAt(i)) same++;
        }
        return same;
    }

    public static void main(String[] args) {
        System.out.println(lcs("CHIAN", "CHAIN"));
        System.out.println(lcs("CABLE", "BLADE"));
        System.out.println(lcs("BELL", "GRIPS"));
    }
}

Common mistakes

  • MistakeUsing plain recursion when subproblems overlap.

    InsteadAdd a memo, or fill a table bottom up.

  • MistakeFilling a table in an order where a cell needs answers not yet computed.

    InsteadFill from the smallest subproblems up, as the recurrence requires.

  • MistakeTrusting a greedy rule for knapsack or arbitrary coin values.

    InsteadUse DP, which considers every option without repeating work.

  • MistakeReturning only the best value when the solution itself is needed.

    InsteadRecord the choice made at each cell and walk back from the answer.

  • MistakeForgetting the base cases, such as best[0] = 0.

    InsteadSet the base cases before filling the rest of the table.

Summary and key terms

  • Dynamic programming solves problems with optimal substructure and overlapping subproblems by solving each subproblem once and storing its answer.
  • Memoization keeps the recursive shape and stores answers in a map, so the Fibonacci numbers need n calls instead of about 1.6ⁿ; tabulation fills a table from the smallest subproblems up with no recursion, and often needs only the last few rows.
  • The method is to define the subproblem, write the recurrence with base cases, choose a filling order, read the answer and record choices to rebuild the solution.
  • DP finds the fewest vouchers for any values where greedy failed, solves the 0/1 knapsack for the trailer in O(n × capacity) instead of O(2ⁿ), and computes edit distance and longest common subsequences in O(m × n), which lets StockRoom suggest the code Kofi meant to type.
Dynamic programming
Solving a problem by solving overlapping subproblems once each and combining their stored answers.
Optimal substructure
The property that the best solution is built from best solutions to subproblems.
Overlapping subproblems
Subproblems that recur many times in a naive recursion.
Memoization
Storing the result of each recursive call so it is computed only once.
Tabulation
Filling a table of subproblem answers from the smallest up, without recursion.
Recurrence
A rule giving a subproblem's answer in terms of smaller subproblems' answers.
0/1 knapsack
Choosing whole items with sizes and values to maximize value within a capacity.
Edit distance
The fewest insertions, deletions and substitutions that turn one string into another.
Longest common subsequence
The longest sequence of characters that appears in two strings in the same order.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Which two properties make a problem suitable for dynamic programming?

    Show answer

    Optimal substructure and overlapping subproblems.

  2. What is the difference between memoization and tabulation?

    Show answer

    Memoization adds a lookup to the recursion; tabulation fills a table bottom up with a loop.

  3. What is the fewest vouchers of 1, 3 and 4 hours that pay 6 hours?

    Show answer

    Two: 3 + 3.

  4. How many cells does the knapsack table need for 5 items and capacity 10?

    Show answer

    6 × 11 = 66, or 55 if row 0 is not counted.

  5. What is the edit distance between CHIAN-11 and CHAIN-11?

    Show answer

    2.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz