Advanced Algorithms · Lecture Notes

Chapter 3: Dynamic Programming

Some recursive solutions are correct but unbearably slow. A method that computes Fibonacci numbers straight from the definition makes more than three hundred million calls for fib(40), although it has only 41 distinct questions to answer. The same questions are asked again and again, and the answers are recomputed from scratch every time. Dynamic programming removes this waste: each subproblem is solved once, its answer is written into a table, and later it is simply read back. These notes first introduce the two conditions of the method, its design steps, and its two ways of implementation (memoization and tabulation). Then the classic problems are taken up one by one: 0/1 and unbounded knapsack, subset sum, longest increasing subsequence, longest common substring, and longest common subsequence. For each problem we write the state and recurrence, fill the table by hand, trace the Java code line by line, and read the solution back from the table. The notes close with other classic examples such as edit distance, coin change, maximum subarray, and matrix-chain multiplication.

Learning outcomes

Recognition
Recognize overlapping subproblems and optimal substructure in a problem; decide when dynamic programming is appropriate and when divide and conquer or a greedy approach is enough.
Formulation
Define a subproblem (a state), write the recurrence and its base cases, and determine the size of the table and the order in which it is filled.
Implementation
Fill in the tables for Fibonacci, 0/1 and unbounded knapsack, subset sum, longest increasing subsequence, longest common substring, and longest common subsequence by hand, and implement them in Java.
Analysis
Compare memoization with tabulation; justify the running times O(n · W), O(m · n), O(n²), and O(n log n); explain pseudo-polynomial time; reconstruct the solution itself from the table.

3.1Basic concepts

3.1.1What is dynamic programming?

A common idea in algorithm design is to split a big problem into smaller problems of the same kind. Divide and conquer uses this idea when the pieces are independent: merge sort splits the array in two, sorts the two halves separately, and merges them. The two halves share no work. In other problems the pieces are entangled. The subproblems of the big problem share subproblems of their own. If such a problem is solved by plain recursion, the same small question is asked many times and answered from scratch each time.

Dynamic programming (DP for short) removes this repetition. The solution of each subproblem is written into a table. When the same subproblem is met again, nothing is computed; the answer is read from the table. The method is used especially for optimization problems, which look for the largest or smallest of something: the largest value, the shortest path, the fewest operations. But the same idea also works for counting and decision problems: "how many different paths are there?", "is there such a subset?"

Definition 3.1

Dynamic programming is an algorithm design method that splits a problem into smaller subproblems, solves each subproblem only once, and reuses the solutions by storing them in a table. In short: DP = recursion + remembering.

This definition has an important consequence. Behind every dynamic programming solution stands a recursive solution. DP does not solve the problem in a different way; it runs the same recursion without the needless repetition. Therefore the first and hardest step of DP design is finding the right recursion. The table is merely a device that stores the values of that recursion.

The name of the method comes from Richard Bellman in the 1950s. The word "programming" in the name does not mean writing code. In those years the word meant planning and scheduling; the name linear programming comes from the same root. Programming in dynamic programming means planning decisions step by step with a table.

3.1.2Overlapping subproblems

Two properties are needed for a problem to benefit from dynamic programming. The first is that the subproblems overlap.

Definition 3.2

A problem has overlapping subproblems if its recursive solution calls the same subproblem more than once. In other words, the number of distinct subproblems is small, but the number of times the recursion calls them is large.

The best-known example is the Fibonacci numbers. If the definition F(n) = F(n − 1) + F(n − 2) is translated directly into code, computing fib(5) calls fib(4) and fib(3). fib(4) in turn calls fib(3), so fib(3) is computed twice. The same thing grows exponentially at smaller arguments: fib(2) is computed three times and fib(1) five times. Figure 3.1 shows these repetitions.

f(5)×1f(4)×1f(3)×2f(2)×3f(1)×5
Figure 3.1: How many times each subproblem is called while computing fib(5). Arrows mean "calls"; the red boxes are subproblems that are solved more than once.

The gap between two numbers decides the gain of DP. For fib(5) there are only six distinct subproblems, fib(0) through fib(5), yet plain recursion makes 15 calls in total. As n grows, the number of distinct subproblems stays at n + 1 while the number of calls grows exponentially. As long as there is repetition to save, the table closes this gap.

If the subproblems do not overlap, a table is useless. In merge sort the two halves of the array are disjoint pieces. No work done to sort the left half is repeated on the right half. A subarray is sorted only once, so an answer written to a table would never be read a second time. Such problems belong to divide and conquer.

Common mistake

It is often assumed that adding a table to any recursive solution speeds it up. A table helps only when the same subproblem is called again. In binary search or merge sort every subproblem is solved once, and a table merely wastes memory.

3.1.3Optimal substructure

The second property is that an optimal solution of the big problem can be built from optimal solutions of the smaller problems. Without it, the subproblem answers in the table are not enough to build the answer to the big problem.

Definition 3.3

A problem has optimal substructure if an optimal solution of the problem can be built from optimal solutions of its subproblems. Bellman stated this property as the principle of optimality: every sub-solution contained in an optimal solution is itself optimal for its own subproblem.

An example makes this property clear. Suppose we look for the maximum-sum subarray of an array, where a subarray is a piece made of adjacent elements. Let V(i) be the largest sum of a piece that ends exactly at element i. The best piece ending at i either consists of a[i] alone or is obtained by appending a[i] to a piece that ends at i − 1. In the second case the piece ending at i − 1 must also be the best one; if a better one existed, using it would increase the sum. The recurrence then follows by itself:

V(i) = max( a[i],   V(i − 1) + a[i] )

Relations of this kind are also called Bellman equations: the value of a state is computed from the optimal value of a previous subproblem. The answer is the largest of all V(i) values. This method is Kadane's algorithm, and it runs in O(n) time.

Optimal substructure does not hold in every problem. Suppose we look for the longest simple path (a path with no repeated vertex) between two vertices of a graph. If the longest simple path from u to w passes through a vertex v, its u–v part need not be the longest simple path from u to v. A longer u–v path may use vertices from the second half of the path. Joining two "best" pieces then produces a path that is not simple. The subproblems cannot be solved independently, which is why no efficient DP is known for this problem. For the shortest-path problem the situation is different: every piece of a shortest path is itself a shortest path. Bellman–Ford and Floyd–Warshall rely on this property.

Common mistake

It is not enough to spot overlapping subproblems and build a table right away. One must first show that combining optimal solutions of the subproblems yields an optimal solution of the big problem. Without optimal substructure, the table produces a fast but wrong answer.

3.1.4Design steps

At first glance dynamic programming solutions look very different from one another: one fills a two-dimensional table, another gets by with a single array. Yet all of them are designed with the same steps. If the steps are followed in order, the solution of a new problem often emerges by itself.

  1. Examine the structure of an optimal solution. What is the last decision in an optimal solution? Which smaller problem remains once that decision is made?
  2. Write the state and the recurrence. Express the subproblem as a state defined by a few integers, e.g. "the first i items and capacity c". Write the value of a state in terms of smaller states (the recurrence). Give separately the values of the smallest states on which the recurrence rests (the base cases).
  3. Determine the order of computation. When a cell is computed, the cells it needs must already be ready.
  4. Determine the size of the table. How many dimensions are needed, and how many values does each dimension take? In knapsack, for example, the table is (n + 1) × (W + 1).
  5. Fill the table. Either with bottom-up loops (tabulation) or with top-down recursion (memoization).
  6. Reconstruct the solution. In most problems we want not only the optimal value but also the choices that produce it. The choices are found by reading the table backwards.

These steps have a simple consequence for running time. Each state is computed once, and computing a state tries a few options. Hence the total time is roughly the number of states times the time to compute one state:

total time ≈ (number of states) × (time per state)

Every complexity in these notes follows from this rule. In knapsack there are (n + 1)(W + 1) states, each computed in O(1) from two options: O(n · W). In longest increasing subsequence there are n states, but each looks at all earlier elements: O(n²). In matrix-chain multiplication each of the O(n²) states tries O(n) split points: O(n³).

3.1.5Memoization and tabulation

A DP recurrence can be run in two ways. Both solve each subproblem once; the difference is in the order in which, and the tool with which, the subproblems are solved.

Memoization works top-down. The recursive solution is written as it is; only the results are kept in a cache. The cache can be an array or a HashMap. At the start of every call the table is consulted: if the answer is there, it is returned at once; otherwise it is computed, stored, and then returned. The computation starts at the big problem and descends to the small problems it needs, so only the subproblems that are really needed are solved. The price is recursion: every call has a cost, and deep recursion can cause a stack overflow (StackOverflowError).

Tabulation works bottom-up. It starts from the smallest subproblem and fills the table in order with loops. There is no recursion and no call overhead, so tabulation is usually faster in practice. In return, the filling order must be chosen correctly in advance: when a cell is reached, the cells it depends on must be ready. Tabulation has one more advantage. If the recurrence uses only the previous row, a single row can be stored instead of the whole table. In knapsack this reduces memory from O(n · W) to O(W).

f0f1f2f3f4f5The call f(5) descends f0f1f2f3f4f5f0, f1, … fill in order
Figure 3.2: Left, memoization: the call fib(5) descends top-down and values are written on the way back. Right, tabulation: f0, f1, … fill from left to right in order.
Table 3.1: Comparison of memoization and tabulation.
Memoization (top-down)Tabulation (bottom-up)
Stylerecursive solution + cachenested loops
Subproblems solvedonly those neededevery cell of the table
Orderdetermined by the recursion itselfmust be chosen correctly in advance
Extra costcall overhead, risk of stack overflownone
Reducing memoryhardeasy if the previous row suffices
Asymptotic timethe same: each subproblem is solved once

Which one to choose depends on the problem. If the state space is large but few states are actually used, memoization does less work. 0/1 knapsack is an example: on an instance with four items and capacity 6, the memoized version computes only 12 of the 28 states. If the whole table is needed anyway and the filling order is clear, tabulation is both faster and safer.

Common mistake

It is sometimes said that "memoization is always faster than tabulation" or the other way round. Their asymptotic times are the same. Tabulation is often faster in practice because it makes no calls; memoization can come out ahead when it skips unnecessary states.

3.1.6DP, divide and conquer, and greedy algorithms

Dynamic programming is understood better when it is considered together with two familiar design methods. All three split the problem into smaller pieces; they differ in the relation between the pieces and in how the choice is made.

Table 3.2: Divide and conquer, dynamic programming, and greedy algorithms.
Divide and conquerDynamic programmingGreedy
Subproblemsindependentoverlappinga single choice at each step
Choicenone; split and combineall options are tried, the best goes into the tablethe best option at the moment is taken, never revisited
Optimality—guaranteed if optimal substructure holdsonly if the greedy-choice property holds
Examplesmerge sort, binary search0/1 knapsack, LCS, Bellman–Fordfractional knapsack, Dijkstra, Kruskal
Costrecurrence, master theoremnumber of states × work per stateusually O(n log n): sorting + one pass
Memoryrecursion stacka table (often O(n · W) or O(m · n))usually O(1) extra

A greedy approach can be seen as a dynamic program that looks at only one option at each step. DP tries all options in a state and writes the best into the table. A greedy algorithm takes the option that looks best at the moment and never examines the others. If it can be proved that this choice always leads to an optimal solution (the greedy-choice property), no table is needed and the algorithm runs much faster. If it cannot be proved, a greedy algorithm may give a wrong answer. 0/1 knapsack is the typical example.

3.1.7Applications

Beyond being a theoretical tool, dynamic programming runs inside many programs that are used every day.

  • Shortest paths. Maps and routing protocols: Bellman–Ford works with the "shortest path using at most k edges" subproblem, and Floyd–Warshall with the "shortest path using only the first k vertices as intermediates" subproblem.
  • String comparison. diff and git find the difference between two files with the longest common subsequence; spell checkers generate suggestions using edit distance.
  • Bioinformatics. Alignment of DNA and protein sequences (Needleman–Wunsch, Smith–Waterman) and determining the folding structure of RNA.
  • Resource allocation. Knapsack, budget and investment planning, production-line scheduling.
  • Compilers and numerical computing. The order of a matrix-chain product, optimal binary search trees, CYK parsing for context-free grammars.
  • Artificial intelligence. The Viterbi algorithm in game-playing programs, speech recognition, and machine translation; the Bellman equation in reinforcement learning.

3.2Fibonacci: memoization and tabulation

The recursive definition of the Fibonacci sequence and the method that translates it directly into code are well known. The goal here is not to explain recursion again. Fibonacci is used to show the two forms of dynamic programming at the smallest scale: the same recurrence is run first with memoization and then with tabulation, and their costs are compared.

3.2.1The cost of plain recursion

The Fibonacci sequence runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …. The base cases are F(0) = 0 and F(1) = 1; for n ≥ 2, F(n) = F(n − 1) + F(n − 2). A method that copies the definition word for word is correct but very slow.

static long fib(int n) {
  if (n <= 1)
    return n;         // base cases
  return fib(n - 1) + fib(n - 2);
}

Let T(n) be the number of calls the method makes. Each call counts as 1 for itself and makes two subcalls: T(n) = T(n − 1) + T(n − 2) + 1, T(0) = T(1) = 1. The solution of this recurrence is T(n) = 2 · F(n + 1) − 1, which is easily verified by induction. Because Fibonacci numbers grow like powers of the golden ratio, the number of calls is Θ(φⁿ), where φ ≈ 1.618. Table 3.3 shows how quickly the gap opens.

Table 3.3: Number of calls made while computing fib(n) with plain recursion and with memoization (counted in Java).
nF(n)Plain recursion: 2 · F(n + 1) − 1Memoization: 2n − 1
55159
105517719
206,76521,89139
30832,0402,692,53759
40102,334,155331,160,28179

fib(40) makes more than three hundred thirty million calls. For fib(50) the number grows to about 4 · 10¹⁰, which takes minutes on an ordinary computer. Yet computing fib(n) involves only n + 1 distinct subproblems: fib(0), fib(1), …, fib(n). The overwhelming majority of the calls ask a question that has already been answered.

f(5)=5f(4)=3f(3)=2f(2)=1f(1)=1f(0)=0f(1)=1f(2)=1f(1)=1f(0)=0f(3)=2f(2)=1f(1)=1f(0)=0f(1)=1
Figure 3.3: The recursion tree of fib(5) after all calls have finished. There are 15 calls; the red boxes mark places where a subproblem that was already solved is computed again.

In the tree of Figure 3.3, fib(3) appears twice, fib(2) three times, fib(1) five times, and fib(0) three times. These counts are themselves Fibonacci numbers: in the tree of fib(n), fib(k) (k ≥ 1) is called exactly F(n − k + 1) times. The amount of repetition grows as fast as the number being computed. This observation is the heart of dynamic programming: when the number of distinct subproblems is small but the recursion calls them many times, storing the results brings a large gain.

3.2.2Memoization

Memoization adds two lines to the body of the method. Every computed value is written into the memo array. Before computing, a call looks into the array; if the value is there, it returns at once.

static long[] memo = new long[50];

static long fib(int n) {
  if (n <= 1) return n;          // base
  if (memo[n] != 0) return memo[n];
  long a = fib(n - 1);
  long b = fib(n - 2);
  memo[n] = a + b;
  return memo[n];
}

Because the memo array is declared static, all calls share the same array. In Java all elements of a new long array are 0, and the code uses 0 to mean "not yet computed". This choice is safe because F(n) is never 0 for n ≥ 2, and the base cases are never written into the array. Since the array has length 50, the code can compute at most fib(49). Choosing long as the return type is also deliberate: F(47) = 2,971,215,073 exceeds int's largest value, 2³¹ − 1 = 2,147,483,647.

The lines work as follows. The first if handles the base cases. The second if is the memo check: if memo[n] is nonzero, the value has been computed before and is returned as is. If it is missing, two subcalls are made, the sum is written to memo[n], and it is returned. Table 3.4 gives a trace of the call fib(5).

Table 3.4: Trace of fib(5) with memoization. The "memo" column gives the values of memo[2..5] after the step (— means not computed).
StepCallEventmemo[2..5]
1fib(5)not in the table; fib(4) is called first— — — —
2fib(4)not in the table; fib(3) is called first— — — —
3fib(3)not in the table; fib(2) is called first— — — —
4fib(2)not in the table; fib(1) is called first— — — —
5fib(1)base case, returns 1— — — —
6fib(0)base case, returns 0; memo[2] = 1 + 0 = 11 — — —
7fib(1)from within fib(3); base case, returns 1; memo[3] = 1 + 1 = 21 2 — —
8fib(2)from within fib(4); memo[2] = 1 is ready, not recomputed; memo[4] = 2 + 1 = 31 2 3 —
9fib(3)from within fib(5); memo[3] = 2 is ready; memo[5] = 3 + 2 = 51 2 3 5
f(5)=5f(4)=3f(3)=2f(2)=1f(1)=1f(0)=0f(1)=1f(2)=1f(3)=2memo—0—112233455
Figure 3.4: fib(5) with memoization: the calls that are actually expanded and the filled memo array. The dashed boxes are the two calls answered straight from the table.

The tree in Figure 3.4 is now a chain. The left arm descends from fib(5) to fib(1). At every level the right child is either a base case or is read directly from the table. In total 9 calls are made. In general every value from fib(2) to fib(n) is computed once. The calls are counted as follows: fib(n) and fib(n − 1) are called once each. For 1 ≤ k ≤ n − 2, fib(k) is called twice: once it is expanded, and once it is answered immediately from the table or as a base case. fib(0) is called once. The total is 2 + 2(n − 2) + 1 = 2n − 1. The exponential time has dropped to linear. The extra memory is O(n): the memo array plus a call stack of n frames at its deepest.

Example 3.1

How many calls do fib(6) with plain recursion and with memoization make?

Plain recursion: 2 · F(7) − 1 = 2 · 13 − 1 = 25 calls. In the tree, fib(2) appears five times and fib(1) eight times. Memoization: fib(6) and fib(5) are called once each. fib(4), fib(3), fib(2), and fib(1) are called twice each; the second calls return immediately from the table or as a base case. fib(0) is called once. The total is 2 + 8 + 1 = 11 = 2 · 6 − 1 calls.

Common mistake

The cache is created as a local variable inside the method. The line long[] memo = new long[50]; allocates a new, empty array on every call. No value is shared, and the running time stays exponential. The cache must live where all calls can see it: a static field, an object field, or an array passed as a parameter.

3.2.3Tabulation

The same recurrence can also be run with a loop. fib(i) depends only on fib(i − 1) and fib(i − 2). If the array is filled from left to right, the two cells each cell needs are ready when it is reached.

static int fibonacci(int n) {
  if (n <= 1) return n;   // n = 0 and n = 1
  int[] fib = new int[n + 1];
  fib[0] = 0;   // base cases
  fib[1] = 1;
  for (int i = 2; i <= n; i++)
    fib[i] = fib[i - 1] + fib[i - 2];
  return fib[n];
}

The method first creates an array of n + 1 elements; in Java all elements start at 0. After the base cases are written, the loop fills every cell from i = 2 to n with one addition. For fibonacci(9) the cells become 1, 2, 3, 5, 8, 13, 21, and 34 in turn. The last cell, fib[9] = 34, is returned. Each cell is computed once: the time is O(n) and the memory is O(n).

00111223345586137218349
Figure 3.5: The fib array after fibonacci(9) finishes. The cells were filled from left to right, one addition each.

The first line is a small but necessary detail. Without it, the array would have a single element for n = 0, and the line fib[1] = 1 would throw an ArrayIndexOutOfBoundsException. if (n <= 1) return n; handles the two base cases before the array is built, so the code works for every n ≥ 0. Also, since the array is int, fibonacci(47) overflows and returns a negative number; in Java this result is −1,323,752,223.

3.2.4O(1) space and a comparison

In the tabulated version, computing fib[i] reads only the last two cells of the array. Older cells are never looked at again. So there is no need to store the whole array; two variables holding the last two values are enough.

static long fib(int n) {
  if (n <= 1) return n;
  long prev = 0, curr = 1;
  for (int i = 2; i <= n; i++) {
    long next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

At each turn of the loop, the variables prev and curr are F(i − 2) and F(i − 1). The new value is computed and the variables are shifted by one step. When the loop ends, curr is F(n). The time is still O(n) and the extra memory is O(1). The long type suffices up to F(92) ≈ 7.5 · 10¹⁸; F(93) overflows.

Table 3.5: Four ways to compute Fibonacci numbers.
MethodTimeExtra memory
Plain recursionΘ(φⁿ)O(n) stack
MemoizationO(n)O(n) table + stack
TabulationO(n)O(n) table
Two variablesO(n)O(1)

The idea of reducing memory rests on a general rule. If a table cell depends on only a bounded number of earlier cells, the cells that will no longer be used can be discarded. In the knapsack table every row depends only on the previous row, so the two-dimensional table can be cut down to a single row. This gain has a price: the discarded cells may be needed to reconstruct the solution. In Fibonacci there is no choice to reconstruct, so nothing is lost.

3.30/1 knapsack

3.3.1The problem

A traveler is going to pack items into a bag that can carry only a limited weight. Each item has a weight and a value. The goal is to maximize the total value in the bag without exceeding the weight limit. Items cannot be divided: an item either goes into the bag whole or not at all. The 0/1 in the name of the problem describes these two options.

Definition 3.4

The 0/1 knapsack problem: given n items and a capacity W, item i has value vᵢ and weight wᵢ. Choose xᵢ ∈ {0, 1} for every item so that Σ vᵢ xᵢ is maximized subject to Σ wᵢ xᵢ ≤ W.

15 kgcapacity4 ₺12 kg2 ₺2 kg2 ₺1 kg1 ₺1 kg10 ₺4 kg
Figure 3.6: A bag with a capacity of 15 kg and five items: 4 ₺ and 12 kg, 2 ₺ and 2 kg, 2 ₺ and 1 kg, 1 ₺ and 1 kg, 10 ₺ and 4 kg.
Example 3.2

Which items should go into the bag of Figure 3.6?

The four items other than the 12 kg one weigh 2 + 1 + 1 + 4 = 8 kg in total; all of them fit and are worth 2 + 2 + 1 + 10 = 15 ₺. If the 12 kg item is chosen, 3 kg remain. The best way to use those 3 kg is the 2 kg and 1 kg items worth 2 ₺ each, for a total of 4 + 2 + 2 = 8 ₺. No choice that takes the 12 kg item can reach 15 ₺. The answer is 15 ₺. Notably, the most expensive item is not part of the optimal solution.

3.3.2Why brute force and greedy choice are not enough

The most direct solution of the problem is to try every selection. Each item has two options; n items give 2ⁿ subsets. For n = 50 this number is 2⁵⁰ ≈ 1.13 · 10¹⁵. Even at a billion subsets per second, it would take more than thirteen days. Brute force is usable only on very small inputs.

The second approach that comes to mind is the greedy choice. The items are sorted by value-to-weight ratio, and starting with the highest ratio, every item that fits is taken. This method sometimes gives the right answer, but not always.

Example 3.3

W = 50 kg; items (60 ₺, 10 kg), (100 ₺, 20 kg), and (120 ₺, 30 kg). What does the greedy choice give, and what is the optimal solution?

The ratios are 6, 5, and 4 ₺/kg. The greedy algorithm first takes the first item (10 kg full), then the second (30 kg full). The third item of 30 kg does not fit into the remaining 20 kg. The result is 160 ₺. Yet the second and third items together weigh exactly 50 kg and bring 220 ₺. By taking the most efficient item the greedy choice makes a correct local decision, but this decision leaves a gap of 20 kg in the bag that cannot be used.

greedy10 kg20 kgoptimal20 kg30 kg160 ₺220 ₺W = 50
Figure 3.7: The greedy choice stops at 160 ₺; the optimal choice is 220 ₺.

The greedy choice is optimal if the items can be divided. That problem is called the fractional knapsack. In the example, if two thirds of the third item could be taken, the greedy algorithm would reach the optimal result with 60 + 100 + 80 = 240 ₺. In the 0/1 case, taking an item changes the later options. The only way to know which choice is better is to try both. That trial means a recursion that branches in two at every item, and the branches meet at the same subproblems. Overlapping subproblems and optimal substructure together open the door to dynamic programming.

3.3.3State and recurrence

The first design step is to look at the last decision. Number the items from 1 to n. In an optimal solution there are only two options for the last item: it is either taken or not taken. If it is not taken, the remaining problem is to pack the first n − 1 items optimally with the same capacity. If it is taken, its value vₙ has been gained, and the remaining problem is to pack the first n − 1 items optimally with capacity W − wₙ. In both cases the remaining problem is of the same kind. Only two numbers change: the number of items and the capacity. The state is defined by these two numbers.

Definition 3.5

K[i][c] is the largest value obtainable with the first i items and capacity c (0 ≤ i ≤ n, 0 ≤ c ≤ W). Base cases and recurrence:

K[0][c] = 0,   K[i][0] = 0
if wᵢ > c:   K[i][c] = K[i − 1][c]
otherwise:   K[i][c] = max( K[i − 1][c],   vᵢ + K[i − 1][c − wᵢ] )

The answer is K[n][W].

The two branches of the recurrence are the values of the two decisions. In the skip branch the capacity stays the same and the best value obtained with the earlier items is used: K[i − 1][c]. In the take branch vᵢ is gained, and the remaining capacity c − wᵢ is filled optimally with the earlier items: vᵢ + K[i − 1][c − wᵢ]. If the item does not fit, there is no take branch. The base cases also agree with intuition: if there are no items, or the capacity is zero, the value is 0.

K[i−1][c−wᵢ]K[i−1][c]K[i][c]skiptake: + vᵢrow i−1 (earlier items)row i
Figure 3.8: Cell K[i][c] is computed from two cells in the row above: K[i − 1][c] directly above it (skip) and K[i − 1][c − wᵢ], wᵢ columns to the left (take).

Figure 3.8 also fixes the order of computation. A cell looks only at the row above. So if the table is filled row by row from top to bottom, the cells a cell needs are ready when it is reached. Within a row the order of the columns does not matter.

3.3.4Filling the table

The recurrence translates directly into two nested loops. The code keeps the items in arrays that start at 0; row i of the table uses item i, that is, the elements v[i - 1] and w[i - 1] of the arrays.

int knapsack(int[] v, int[] w, int W) {
  int n = v.length;
  int[][] K = new int[n + 1][W + 1];
  for (int i = 1; i <= n; i++)
    for (int c = 1; c <= W; c++) {
      int vi = v[i - 1], wi = w[i - 1];
      if (wi > c)            // does not fit
        K[i][c] = K[i - 1][c];
      else                   // skip / take
        K[i][c] = Math.max(K[i - 1][c],
                    vi + K[i - 1][c - wi]);
    }
  return K[n][W];
}

new int[n + 1][W + 1] initializes all cells to 0, so row 0 and column 0 supply the base cases by themselves. This is why the loops start at 1. The inner if tests whether the item fits. If it does not, the value above is copied; if it does, the larger of the two branches is written.

As an example take four items and W = 6. The items, as (value, weight), are (5, 4), (4, 3), (3, 2), and (2, 1). The table has size (n + 1) × (W + 1) = 5 × 7. Table 3.6 gives the filled table.

Table 3.6: The table K[i][c]; items (5, 4), (4, 3), (3, 2), (2, 1), W = 6.
ivᵢwᵢc = 0123456
0——0000000
1540000555
2430004555
3320034578
4210235679

Let us follow the rows one by one.

  • Row 1 (5, 4). For c = 1, 2, 3 the item does not fit; the 0 above is copied. At c = 4, max(0, 5 + K[0][0]) = 5. At c = 5 and 6 the same computation gives 5; a single item can be taken only once.
  • Row 2 (4, 3). At c = 3 the second item fits for the first time: max(0, 4 + K[1][0]) = 4. At c = 4 the skip branch gives 5 and the take branch gives 4 + K[1][1] = 4; 5 stays. At c = 5 and 6 it also stays 5: the two items together weigh 7 kg and do not fit.
  • Row 3 (3, 2). At c = 2, 3 is written. At c = 3 skipping gives 4 and taking gives 3 + K[2][1] = 3; 4 stays. At c = 5 the take branch gives 3 + K[2][3] = 3 + 4 = 7, which beats the 5 of the skip branch. At c = 6, 3 + K[2][4] = 3 + 5 = 8 is written.
  • Row 4 (2, 1). The lightest item fits in every column. c = 1: max(0, 2) = 2. c = 3: max(4, 2 + K[3][2]) = max(4, 5) = 5. c = 4: max(5, 2 + 4) = 6. c = 5: max(7, 2 + 5) = 7; the two branches are equal and skipping is kept. c = 6: max(8, 2 + K[3][5]) = max(8, 9) = 9.
c (capacity) →ivw0123456000000001540000555243000455533200345784210235679
Figure 3.9: The table is filled. The answer is K[4][6] = 9; 24 cells were computed, each in O(1).

The answer is in the bottom-right cell: K[4][6] = 9. Each row of the table answers a question: "with only the first i items available, what is the best value for each capacity?" Row 3, for example, says that with items (5, 4), (4, 3), and (3, 2), a 5 kg bag can carry a value of at most 7 ₺.

Common mistake

In row i, the item data is read with v[i] and w[i]. The table has n + 1 rows but the arrays have n elements. If v[i] is written, every row uses the next item, and the last row causes an ArrayIndexOutOfBoundsException. The correct form is v[i - 1].

3.3.5Reconstructing the solution

The table gives only the largest value. Which items were chosen is hidden inside the table and is found by reading it from the end back to the start. This process is called traceback.

The rule is simple. If K[i][c] ≠ K[i − 1][c], the value can have increased only by taking item i; the item was taken, and the capacity becomes c ← c − wᵢ. If they are equal, the same value is obtainable without the item; the item counts as not taken and c does not change. In both cases we move up one row.

Table 3.7: Traceback from cell K[4][6] = 9.
CellComparisonDecisionNew c
K[4][6] = 9≠ K[3][6] = 8item 4 taken (v = 2, w = 1)6 − 1 = 5
K[3][5] = 7≠ K[2][5] = 5item 3 taken (v = 3, w = 2)5 − 2 = 3
K[2][3] = 4≠ K[1][3] = 0item 2 taken (v = 4, w = 3)3 − 3 = 0
K[1][0] = 0= K[0][0] = 0item 1 not taken0
c (capacity) →ivw0123456000000001540000555243000455533200345784210235679
Figure 3.10: The path followed by the traceback. The chosen items are 2, 3, and 4: value 4 + 3 + 2 = 9, weight 3 + 2 + 1 = 6 = W.

The traceback makes one comparison per row; its running time is O(n). The same rule translates easily into code. The following method takes the filled table and the weights and returns the numbers of the chosen items (starting from 1).

List<Integer> traceback(int[][] K, int[] w, int W) {
  List<Integer> chosen = new ArrayList<>();
  int c = W;
  for (int i = K.length - 1; i >= 1; i--)
    if (K[i][c] != K[i - 1][c]) {   // value grew: item i taken
      chosen.add(0, i);
      c -= w[i - 1];
    }
  return chosen;
}

For the example table the method returns [2, 3, 4]. Counting an item as not taken in case of equality means that, if there are several optimal solutions, one of them is picked. For example, in cell K[4][5] = 7 the two branches were equal; a traceback starting from that cell does not take item 4 and finds items (4, 3) and (3, 2).

3.3.6Complexity and pseudo-polynomial time

The table has (n + 1)(W + 1) cells, and each cell is computed in constant time. The time and memory are O(n · W). At first sight this looks like polynomial time. But there is an important subtlety here.

The running time of an algorithm is measured against the size of the input, that is, the number of bits needed to write it down. Writing n items takes space proportional to n. But writing the number W takes only log₂ W bits. W = 10⁹ is written with thirty bits, yet the table needs 10⁹ columns. When the number of bits of W grows by one, the value of W and the width of the table double. The running time is exponential in the length of the input.

Definition 3.6

An algorithm whose running time is polynomial not in the length of the input but in the value of a number in the input is called a pseudo-polynomial time algorithm. The O(n · W) DP for 0/1 knapsack is of this kind.

This distinction has a practical consequence. 0/1 knapsack is an NP-hard problem; no known algorithm solves it in polynomial time on every input. DP does not change this fact. It only makes the problem practically solvable when W is small, for example a few thousand or a few million. If the weights are in grams and the capacity is a few tons, the table reaches billions of columns and cannot be built.

Common mistake

O(n · W) is taken to be polynomial, and it is said that "0/1 knapsack is solved in polynomial time by DP". W is a number; it occupies log W bits in the input. The running time is exponential in this number of bits.

3.3.7A one-dimensional table

Row i uses only row i − 1. This observation reduces the memory to O(W): a one-dimensional dp array is kept. The items are processed in order; for each item the array is updated in place, from the old row to the new row.

int[] dp = new int[W + 1];
for (int i = 0; i < n; i++)
  for (int c = W; c >= w[i]; c--)
    dp[c] = Math.max(dp[c],
                     v[i] + dp[c - w[i]]);
return dp[W];

The most important detail of the code is the direction of the inner loop: the capacity is scanned from large to small. The reason is this. When dp[c] is updated, the dp[c - w[i]] that is read must be the value of the old row; that is, item i must not have been taken into account yet. When scanning from large to small, the cells with c − wᵢ < c have not yet been updated in this round and still carry their old values. If the scan went from small to large, dp[c - w[i]] would already have been updated in this round, and the same item could be taken twice. The lower bound of the loop, c >= w[i], never visits capacities that cannot hold the item. In those cells the value does not change; it counts as copied from the old row.

Table 3.8: One-dimensional 0/1 knapsack; items (5, 4), (4, 3), (3, 2), (2, 1), W = 6. Each row is dp[0..6] after that item has been processed.
Item (v, w)Changed cells (from c = 6 downward)dp[0..6]
initial—0 0 0 0 0 0 0
0: (5, 4)dp[6]: 0 → 5, dp[5]: 0 → 5, dp[4]: 0 → 50 0 0 0 5 5 5
1: (4, 3)dp[3]: 0 → 40 0 0 4 5 5 5
2: (3, 2)dp[6]: 5 → 8, dp[5]: 5 → 7, dp[2]: 0 → 30 0 3 4 5 7 8
3: (2, 1)dp[6]: 8 → 9, dp[4]: 5 → 6, dp[3]: 4 → 5, dp[1]: 0 → 20 2 3 5 6 7 9

Each row is identical to the row with the same number in the two-dimensional table. For example, while item 0 is processed, dp[6], dp[5], and dp[4] become 5 in turn. The cells read in the meantime, dp[2], dp[1], and dp[0], have not changed yet and are 0; the item is taken once. The result is dp[6] = 9. Since the code numbers items from 0, the selection reads "items 1, 2, 3": 4 + 3 + 2. In the numbering of the two-dimensional table, these are items 2, 3, and 4.

dp00213253647596itemv=5 w=4v=4 w=3v=3 w=2v=2 w=1
Figure 3.11: The single-row table after four items have been processed: dp[6] = 9, the same as the bottom-right cell of the two-dimensional table.
Example 3.4

For the same four items, what happens if the inner loop is mistakenly written from small to large (for (int c = w[i]; c <= W; c++))?

While item 3 (2, 1) is processed, dp[1] becomes 2; then dp[2] = max(3, 2 + dp[1]) = 4. This computation uses the dp[1] that was just updated, that is, it takes the same item a second time. The chain continues: dp[3] = 6, dp[4] = 8, dp[5] = 10, dp[6] = 12. The result is 12, as if six copies of the lightest item had been taken. This is not a 0/1 solution; it is the answer of the unbounded knapsack.

The one-dimensional version has a price. Since the intermediate rows are deleted, traceback is no longer possible. If the chosen items are needed, a separate boolean[][] take table is kept that stores the decision for each item and capacity. This table is also of size n · W, but it takes less space because it stores boolean instead of int.

3.3.8The top-down solution

The same recurrence can also be written with memoization. Here the subproblem is defined as "the largest value obtainable from item i onward with capacity c"; the items are scanned from first to last. This definition is the mirror image of the one in tabulation and gives the same answer.

Integer[][] memo;   // memo[i][c]: best from item i onward, capacity c

int f(int[] v, int[] w, int i, int c) {
  if (i == v.length) return 0;              // no items left
  if (memo[i][c] != null) return memo[i][c];
  int best = f(v, w, i + 1, c);             // skip
  if (w[i] <= c)                            // take
    best = Math.max(best, v[i] + f(v, w, i + 1, c - w[i]));
  memo[i][c] = best;
  return best;
}

int knapsackMemo(int[] v, int[] w, int W) {
  memo = new Integer[v.length][W + 1];
  return f(v, w, 0, W);
}

The cache is of type Integer[][]. Integer objects start as null, and null means "not yet computed". If int[][] were used, the value 0 would mean both "not computed" and "the real answer is 0", and states whose answer is 0 would be recomputed again and again. The method first checks the base case: if no items are left, the value is 0. Then it checks the cache. If the value is missing, it computes the skip branch, computes the take branch too if the item fits, and stores the larger one.

In the example knapsackMemo(v, w, 6) returns 9. The cache has 4 × 7 = 28 cells, but only 12 of them are filled. The recursion starting from the root descends only to capacities that can really be reached: at item 0 only c = 6; at item 1, c = 6 and 2; at item 2, 6, 3, and 2; at item 3, 6, 4, 3, 1, 2, and 0. When the weights are large and few, this difference grows even more. For example, if all weights are multiples of 1000, only capacities that are multiples of 1000 are reached.

3.4Unbounded knapsack

3.4.1Problem and recurrence

In some problems the items are given not one by one but as types, and any number of each type may be taken. A shipping company can load as many boxes of the same size as it wishes; a cutting machine can cut as many pieces of the same length as it wishes. This problem is called the unbounded knapsack. Everything else is the same as in 0/1 knapsack: the total profit is maximized without exceeding the capacity.

The state is again defined by two numbers, but this time the item types are numbered from 0: dp[i][c] is the largest profit obtainable with item types 0 through i and capacity c. The structure of the last decision is similar. If no copy of type i is taken, the answer is dp[i − 1][c]. If at least one is taken, profitᵢ is gained and a capacity of c − weightᵢ remains. In this remaining capacity the same type can be taken again. So the remaining problem lies not in row i − 1 but again in row i.

dp[i][c] = max( dp[i − 1][c],   profitᵢ + dp[i][c − weightᵢ] )    (if weightᵢ ≤ c)

If the item does not fit, only the first branch remains. Since row indices start at 0, we take dp[−1][c] = 0: with no item types the profit is 0. The only difference from 0/1 knapsack is the row that the "take" branch looks at.

i−1isame row: c − weightᵢ
Figure 3.12: In unbounded knapsack the take branch looks at the cell c − weightᵢ in the same row: after an item is taken it can be taken again.

This difference also affects the order of computation. A cell now depends on a cell to its left in the same row. If the row is filled from left to right, that cell is ready. Rows are still scanned from top to bottom.

3.4.2Filling the table

As an example take four item types: profits [15, 50, 60, 90], weights [1, 3, 4, 5], capacity 8. The table has size 4 × 9. In the first row only type 0 (profit 15, 1 kg) can be used.

Table 3.9: The unbounded knapsack table; profits [15, 50, 60, 90], weights [1, 3, 4, 5], capacity 8.
iprofitweightc = 012345678
01510153045607590105120
150301530506580100115130
260401530506580100115130
390501530506590105120140

The rows are computed as follows.

  • Row 0. The capacity 0 column is 0. At c = 1 the only option is to take type 0: 15 + dp[0][0] = 15. At c = 2, 15 + dp[0][1] = 30: the same row was used again, that is, two items of type 0 were taken. The row thus fills with multiples of 15: dp[0][c] = 15c.
  • Row 1 (50, 3 kg). At c = 1, 2 the item does not fit and the row above is copied. c = 3: max(45, 50 + dp[1][0]) = 50. c = 4: max(60, 50 + dp[1][1]) = 65. c = 6: max(90, 50 + dp[1][3]) = max(90, 100) = 100; here dp[1][3] is itself a cell that contains type 1. 100 is two items of 50. c = 8: max(120, 50 + dp[1][5]) = 130.
  • Row 2 (60, 4 kg). The item of 60 cannot beat the row above in any column. At c = 8, for example, 60 + dp[2][4] = 60 + 65 = 125 < 130. The row is a copy of the row above.
  • Row 3 (90, 5 kg). c = 5: max(80, 90 + 0) = 90. c = 6: max(100, 90 + dp[3][1]) = 105. c = 7: max(115, 90 + 30) = 120. c = 8: max(130, 90 + dp[3][3]) = max(130, 140) = 140.
capacity →profitwt.i01234567815100153045607590105120503101530506580100115130604201530506580100115130905301530506590105120140
Figure 3.13: The filled table. The answer is dp[3][8] = 140 = 90 + dp[3][3]; dp[3][3] = 50 is one item of type 1.

The answer is dp[3][8] = 140. Traceback is done as in 0/1, with one difference: when a type is taken, we stay in the same row. Since dp[3][8] = 140 ≠ dp[2][8] = 130, one item of type 3 has been taken and c = 3. Since dp[3][3] = dp[2][3] = 50, we move up. dp[2][3] = dp[1][3], up again. dp[1][3] = 50 ≠ dp[0][3] = 45: one item of type 1 has been taken and c = 0. The solution is one item of 90 (5 kg) and one item of 50 (3 kg).

3.4.3One-dimensional solution and loop direction

In unbounded knapsack the rows can be merged completely. Since any number of each type may be taken, the best value for capacity c can be written by looking at the last item taken. If the last item is j, the remaining capacity is c − wⱼ, and there too all types are free:

dp[c] = max { dp[c − wⱼ] + vⱼ : wⱼ ≤ c },    dp[0] = 0

static int unboundedKnapsack(int[] w, int[] v, int W) {
  int[] dp = new int[W + 1];       // dp[c]: best for capacity c
  for (int c = 1; c <= W; c++)
    for (int j = 0; j < w.length; j++)
      if (w[j] <= c)
        dp[c] = Math.max(dp[c], dp[c - w[j]] + v[j]);
  return dp[W];
}

The outer loop raises the capacity from 1 to W, and the inner loop tries every type. When dp[c] is computed, all smaller capacities are ready. For the example the resulting array is dp = [0, 15, 30, 50, 65, 90, 105, 120, 140], the same as the last row of the two-dimensional table. The time is O(n · W) and the memory is O(W).

The relation between the one-dimensional 0/1 knapsack and this code is instructive. Both perform the following update on a single array: dp[c] = max(dp[c], v + dp[c - w]). The difference is in the loop direction. If the capacity is scanned from small to large, dp[c - w] has already been updated in this round and may contain the item; the item can be taken again, and the result is unbounded knapsack. If the capacity is scanned from large to small, dp[c - w] carries its old value; the item is taken at most once, and the result is 0/1. The same one-line update solves two different problems, merely by the direction of the loop.

Example 3.5

There is a single item: value 10, weight 3; capacity 9. What is dp[9] if the one-dimensional table is filled in the two directions?

From large to small: at c = 9, dp[6] is still 0, so dp[9] = 10; 10 is also written at c = 6 and c = 3. The result is 10; the item is taken once. From small to large: dp[3] = 10, dp[6] = 10 + dp[3] = 20, dp[9] = 10 + dp[6] = 30. The item has been taken three times. 10 is the answer of 0/1; 30 is the answer of unbounded knapsack.

Common mistake

In one-dimensional 0/1 knapsack the capacity is scanned from small to large. The code compiles, runs, and returns a plausible-looking number, but that number is the answer of unbounded knapsack. The easiest way to catch the bug is to test a small example with a single item and check whether the result exceeds the item's value.

3.4.4Code trace

A trace of the one-dimensional code shows which option wins at each capacity. The version below is the tracing code from the slides and does the same job as the one above.

static int unboundedKnapsack(
    int[] w, int[] v, int W) {
  int[] dp = new int[W + 1];  // dp[c]
  for (int c = 1; c <= W; c++)
    for (int j = 0; j < w.length; j++)
      if (w[j] <= c)
        dp[c] = Math.max(dp[c],
                  dp[c - w[j]] + v[j]);
  return dp[W];
}
Table 3.10: Trace of unboundedKnapsack(w, v, 8); profits [15, 50, 60, 90], weights [1, 3, 4, 5]. In each row, the candidates from the types that fit and the winning value.
cCandidates dp[c − wⱼ] + vⱼdp[c]
1dp[0] + 15 = 1515
2dp[1] + 15 = 3030
3dp[2] + 15 = 45, dp[0] + 50 = 5050
4dp[3] + 15 = 65, dp[1] + 50 = 65, dp[0] + 60 = 6065
5dp[4] + 15 = 80, dp[2] + 50 = 80, dp[1] + 60 = 75, dp[0] + 90 = 9090
6dp[5] + 15 = 105, dp[3] + 50 = 100, dp[2] + 60 = 90, dp[1] + 90 = 105105
7dp[6] + 15 = 120, dp[4] + 50 = 115, dp[3] + 60 = 110, dp[2] + 90 = 120120
8dp[7] + 15 = 135, dp[5] + 50 = 140, dp[4] + 60 = 125, dp[3] + 90 = 140140

The row c = 2 shows the source of unboundedness: dp[1] had been updated in this round and contained type 0 once; adding 15 to it again means two items of the same type have been taken. In the last row two candidates reach 140: dp[5] + 50 and dp[3] + 90. Both describe the same selection: one item of 50 (3 kg) and one item of 90 (5 kg). The selection 15 + 15 + 50 + 60, which also gives 140, weighs 9 kg and does not fit into the bag. The table has tried all combinations in O(n · W) time without counting them one by one.

dp00151302503654905105612071408itemw=1 v=15w=3 v=50w=4 v=60w=5 v=90
Figure 3.14: The dp array at the end of the trace; dp[8] = 140.

3.5Subset sum

3.5.1Problem and recurrence

Suppose we are given an array of non-negative integers and a target value (target ≥ 0). Is there a subset whose sum is exactly equal to the target? This question is not an optimization but a decision problem: the answer is yes or no. The problem is called subset sum.

1010005588662244target sum = 155 + 8 + 2 = 15✓✓✓
Figure 3.15: In the array 10, 0, 5, 8, 6, 2, 4 with target 15: for example, choosing 5, 8, and 2 gives a sum of 15.

The last decision is again whether an element is chosen. If the last element is not chosen, the question is whether the same target can be reached with the first n − 1 elements. If it is chosen, the target decreases by the element. The state is defined by two numbers, and its value is a Boolean.

Definition 3.7

dp[i][j] is true if a subset with sum exactly j can be formed from the first i elements, and false otherwise.

dp[i][0] = true,   dp[0][j] = false  (j > 0)
dp[i][j] = dp[i − 1][j]  or  ( aᵢ ≤ j  and  dp[i − 1][j − aᵢ] )

Column 0 is true in every row, because the empty set gives the sum 0. In row 0 no sum greater than zero can be obtained. The recurrence has the same form as that of 0/1 knapsack: a logical or replaces the max of knapsack, and instead of adding up values there is only reachability. Subset sum can also be seen as the special case of knapsack in which "value = weight". Let the value of each element equal its weight and let the capacity be the target. If the answer of the knapsack equals the target, the desired subset exists.

3.5.2Table and reconstruction

Let the array be a = 10, 0, 5, 8, 6, 2, 4 and the target 15. The table has size 8 × 16. Instead of writing every row with all its cells, it is more readable to list the sums reachable in that row. A row keeps all the sums of the previous row and also adds new sums by adding aᵢ to each of them (those exceeding the target are left out).

Table 3.11: The subset sum table row by row; a = 10, 0, 5, 8, 6, 2, 4, target 15. The columns that are true in the row are listed.
iaᵢReachable sums (dp[i][j] true)New
0—0—
1100, 1010
200, 10none
350, 5, 10, 155, 15
480, 5, 8, 10, 13, 158, 13
560, 5, 6, 8, 10, 11, 13, 14, 156, 11, 14
620, 2, 5, 6, 7, 8, 10, 11, 12, 13, 14, 152, 7, 12
740, 2, 4, 5, 6, …, 15 (all except 1 and 3)4, 9

Row 2 is interesting: adding 0 changes no sum, and the row is a copy of the row above. The target 15 becomes reachable for the first time in row 3: 10 and 5 together. The last cell dp[7][15] is true; the answer is yes.

The traceback starts from the last cell. If dp[i − 1][j] is true, the sum j can be formed without aᵢ; the element is not chosen and we move up. If it is false, the sum can be formed only with aᵢ; the element is chosen and j ← j − aᵢ.

  • dp[7][15] = dp[6][15] = true: 4 is not chosen. By the same reasoning 2, 6, and 8 are not chosen either; we move up to row 4.
  • dp[3][15] is true but dp[2][15] is false: 5 is chosen; j = 15 − 5 = 10.
  • dp[2][10] = dp[1][10] = true: 0 is not chosen.
  • dp[1][10] is true but dp[0][10] is false: 10 is chosen; j = 0 and the reading ends.
j (sum) →iaᵢ01234567891011121314150—✓···············110✓·········✓·····20✓·········✓·····35✓····✓····✓····✓48✓····✓··✓·✓··✓·✓56✓····✓✓·✓·✓✓·✓✓✓62✓·✓··✓✓✓✓·✓✓✓✓✓✓74✓·✓·✓✓✓✓✓✓✓✓✓✓✓✓
Figure 3.16: The filled table and the traceback path. The traceback finds the subset {5, 10}: 10 + 5 = 15.

In this array there are six subsets whose sum is 15: {10, 5}, {5, 8, 2}, {5, 6, 4}, and the versions of each with 0 added. The traceback gives only one. Which one it gives depends on the tie-breaking rule. Since the rule here is "do not choose if it is possible without the element", the reading leans toward the solution that uses elements from the start of the array.

3.5.3Code and analysis

boolean subsetSum(int[] a, int target) {
  int n = a.length; // a[i] ≥ 0, target ≥ 0
  boolean[][] dp = new boolean[n + 1][target + 1];
  for (int i = 0; i <= n; i++)
    dp[i][0] = true;           // empty set
  for (int i = 1; i <= n; i++) {
    int x = a[i - 1];
    for (int j = 1; j <= target; j++)
      dp[i][j] = dp[i - 1][j]  // x not taken
        || (x <= j && dp[i - 1][j - x]);
  }
  return dp[n][target];
}

In Java a new boolean array starts as false. The first loop makes column 0 true. The expression in the inner loop is a literal translation of the recurrence. The short-circuit behavior of the || operator is useful here: if dp[i - 1][j] is true, the right-hand side is never evaluated. The test x <= j on the right, thanks to the short circuit of &&, prevents accessing the array when j - x is negative. This guarantee rests on the precondition that the elements and the target are non-negative: since x ≥ 0, j - x never exceeds j, and since target ≥ 0, the table can be built. For negative elements a separate table with a shifted range of sums is needed.

The time and memory are O(n · target). This too is a pseudo-polynomial time: if the target is large, the table cannot be built. Subset sum is an NP-complete problem; DP makes it practical only when the target is small. As in 0/1 knapsack, the memory can be reduced to one dimension. For this, j is scanned from large to small so that each element is used at most once.

Example 3.6

The partition problem. Can the array {1, 5, 11, 5} be split into two parts with equal sums?

The total is S = 22. If one part has sum S/2 = 11, the other part has sum 11 as well. The question turns into subset sum with target 11. {11} or {1, 5, 5} gives this sum; the answer is yes. If S were odd, the answer would be no without any computation.

Common mistake

Column 0 is not initialized to true. The table stays false throughout and no sum looks reachable; the answer is "no" on every input. The sum of the empty set is 0, and this holds in every row.

3.5.4Code trace

Let us trace the line-by-line behavior of the code on a smaller example: subsetSum({3, 34, 4, 12, 5, 2}, 9). The table has (n + 1) × (target + 1) = 7 × 10 = 70 cells.

Table 3.12: Trace of subsetSum({3, 34, 4, 12, 5, 2}, 9); the columns that are true in each row.
ixj with dp[i][j] trueExplanation
0—0only the empty set
130, 3new sum: 3
2340, 334 > 9: does not fit for any j, the row is copied
340, 3, 4, 7new sums: 4, 7
4120, 3, 4, 712 > 9: the row is copied
550, 3, 4, 5, 7, 8, 9new: 5, 8, 9; dp[5][9] = dp[4][4] → 4 + 5 = 9
620, 2, 3, 4, 5, 6, 7, 8, 9new: 2, 6
0123456789–0T·········31T··T······342T··T······43T··TT··T··124T··TT··T··55T··TTT·TTT26T·TTTTTTTTx
Figure 3.17: The end of the trace: dp[6][9] = true. T marks true cells and dots mark false cells.

The method returns true. There are two subsets with sum 9: {4, 5} and {3, 4, 2}. The traceback starts at dp[6][9]; since dp[5][9] is true, 2 is not chosen. Since dp[4][9] is false, 5 is chosen and j = 4. 12 is not chosen; since dp[2][4] is false, 4 is chosen and j = 0. The subset found is {4, 5}. If the target 30 were asked for the same array, the answer would be no: 34 can never be used, and the sum of the other elements is 3 + 4 + 12 + 5 + 2 = 26 < 30.

3.6Longest increasing subsequence

3.6.1Subsequence and substring

The three problems in this and the next two sections (LIS, common substring, LCS) concern pieces of a sequence. The word "piece" is used in two different senses, and confusing the two is the leading source of mistakes on this topic.

Definition 3.8

A subsequence of a sequence is a sequence obtained by skipping some elements and keeping the order of the remaining ones. The chosen elements need not be adjacent.

A substring (or contiguous subarray) of a sequence is a piece made of consecutive elements.

In the string "GXTXAYB" the elements G, T, A, B occur at positions 0, 2, 4, and 6. Since their relative order is kept, "GTAB" is a subsequence. Since the elements are not adjacent, it is not a substring. In contrast, "XAY" occurs contiguously at positions 3, 4, and 5; it is both a substring and a subsequence. Every substring is also a subsequence; the converse is not true. A sequence of length n has 2ⁿ subsequences, but only n(n + 1)/2 nonempty contiguous pieces.

Definition 3.9

The longest increasing subsequence (LIS) is the longest among the subsequences whose elements are strictly increasing.

As an example take the following arrangement of the numbers 0 through 15: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. One LIS of this sequence is 0, 2, 6, 9, 11, 15, and its length is 6.

0841221061419513311715
Figure 3.18: The elements 0, 2, 6, 9, 11, 15 are picked while skipping the others; their relative order is kept and their values increase.

The same sequence has other LISs as well. For example, 0, 4, 6, 9, 13, 15 and 0, 2, 6, 9, 13, 15 are also increasing subsequences of length 6; this sequence has four different LISs in total. The LIS need not be unique, but its length is. DP first finds this length; if the sequence itself is needed, it is read back with extra information.

3.6.2The O(n²) dynamic program

Choosing the right state is the key to this problem. "The LIS length of the first i elements" is not a good state: knowing this value does not tell whether element i + 1 can extend that sequence, because we do not know which number the sequence ends with. The state must fix the endpoint.

Definition 3.10

dp[i] is the length of the longest increasing subsequence that ends exactly at a[i].

dp[i] = 1 + max { dp[j] : j < i,   a[j] < a[i] }

If there is no such j, dp[i] = 1. The answer is max dp[i].

The meaning of the recurrence is this. In an increasing subsequence ending at a[i], the element before a[i] is some a[j] that lies to the left and is smaller than a[i]. a[i] is appended to the longest sequence ending at that element. All candidates are tried and the longest is chosen. If there is no smaller element before it, a[i] alone is a sequence of length 1. The answer is not the last cell: the LIS can end anywhere in the sequence.

Table 3.13 gives all dp values of the 16-element example. The "prev" row is the j that gives the largest dp[j]; in case of a tie the first j from the left was chosen.

Table 3.13: dp and predecessor indices for the 16-element sequence.
i0123456789101112131415
a[i]0841221061419513311715
dp[i]1223233424353546
prev—0010123062949611

Let us write out the computation of a few cells in detail. At i = 3, a[3] = 12; the candidates on the left are 0, 8, and 4, with dp values 1, 2, 2. The largest is the 2 at j = 1: dp[3] = 3 (0, 8, 12). At i = 9, a[9] = 9; the candidates are 0, 8, 4, 2, 6, and 1. Of these, the one ending the longest sequence is 6 (dp[6] = 3): dp[9] = 4 (0, 4, 6, 9). At i = 15, a[15] = 15 is larger than all elements; the largest dp value among the candidates is 5, first seen at j = 11: dp[15] = 6.

0123456789101112131415a0841221061419513311715dp1223233424353546prev—0010123062949611
Figure 3.19: The largest dp is 6 (i = 15). The predecessor indices are followed: 15 → 11 → 9 → 6 → 2 → 0; the LIS is 0, 4, 6, 9, 13, 15.

The sequence itself is read back from the predecessor indices. We start at the index holding the largest dp value and jump along predecessor indices: 15 → 11 → 9 → 6 → 2 → 0. The elements at these indices, from last to first, are 15, 13, 9, 6, 4, 0; reversed, this gives 0, 4, 6, 9, 13, 15. This differs from the LIS of Figure 3.18 but has the same length. The cause of the difference is the tie-breaking rule: at i = 15 both j = 11 and j = 13 are candidates with dp value 5, and the first one seen is chosen.

3.6.3Code and trace

static int lis(int[] a) {
  int n = a.length, best = 0;
  int[] dp = new int[n];
  for (int i = 0; i < n; i++) {
    dp[i] = 1;               // alone
    for (int j = 0; j < i; j++)
      if (a[j] < a[i] && dp[j] + 1 > dp[i])
        dp[i] = dp[j] + 1;   // extend
    best = Math.max(best, dp[i]);
  }
  return best;
}

For each i, the outer loop first writes dp[i] = 1: the element alone is a sequence. The inner loop tries every j to the left. The condition a[j] < a[i] ensures that the sequence is increasing, and dp[j] + 1 > dp[i] ensures that only a longer sequence is accepted. The strict greater-than keeps the first j on a tie. At the end of each round best is updated. The inner loop runs 0 + 1 + … + (n − 1) = n(n − 1)/2 times in total; the time is O(n²) and the memory is O(n).

Tracing the code on a shorter sequence shows the effect of the lines clearly: lis({5, 2, 8, 6, 3, 6, 9, 7}).

Table 3.14: Trace of lis({5, 2, 8, 6, 3, 6, 9, 7}).
ia[i]Smaller on the leftChosen j (dp[j])dp[i]best
05none—11
12none—11
285, 20 (1)22
365, 20 (1)22
4321 (1)22
565, 2, 34 (2)33
695, 2, 8, 6, 3, 65 (3)44
775, 2, 6, 3, 65 (3)44
adp502182633465967711222344
Figure 3.20: The end of the trace: best = 4. One LIS is 2, 3, 6, 9 (the chain with dp values 1, 2, 3, 4).

The row i = 5 shows why the state is defined as "ending at a[i]". There are three elements smaller than a[5] = 6: 5, 2, and 3. 5 and 2 are each the end of a sequence of their own (dp = 1). 3 is the end of the sequence 2, 3 (dp = 2). 6 extends the longest chain: 2, 3, 6. The dp value of the last element 7 is 4 and equals best; this is a coincidence. If a 1 were appended to the sequence, the last cell would be 1 and the answer would still be 4.

To build the sequence, the predecessor index of each element is stored. The following method adds a prev array to lis and follows the chain backwards from where the longest sequence ends.

List<Integer> lisSeq(int[] a) {
  int n = a.length, last = 0;
  int[] dp = new int[n], prev = new int[n];
  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[last]) last = i;
  }
  LinkedList<Integer> lis = new LinkedList<>();
  for (int i = last; i != -1; i = prev[i])
    lis.addFirst(a[i]);
  return lis;
}

For the example sequence the method returns [2, 3, 6, 9], and for the 16-element sequence [0, 4, 6, 9, 13, 15]. LinkedList.addFirst offsets the fact that the traceback proceeds from the end to the start: since elements are added at the front, the list comes out in the correct order.

Common mistake

The method returns dp[n - 1] instead of best. In the sequence {5, 1, 6, 2, 7, 0}, dp = [1, 1, 2, 2, 3, 1]. The last element 0 cannot extend any sequence; dp[5] = 1 is returned. The correct answer is 3 (5, 6, 7 or 1, 2, 7).

3.6.4Active lists

The O(n²) algorithm looks at all elements to the left at every element. For a faster method we use the following observation: if there are two increasing sequences of the same length, the one with the smaller last element is always better. If a number that comes later can extend the one with the larger last element, it can also extend the one with the smaller last element; the converse is not true. So it suffices to keep a single list for each length: among the increasing lists of that length, the one with the smallest last element. These lists are called active lists.

When a new element x arrives there are three cases:

  1. If x is smaller than the last elements of all active lists, a new list [x] of length 1 starts and replaces the old list of length 1.
  2. If x is larger than all last elements, the longest list is copied and x is appended; the number of lists grows by one.
  3. Otherwise, the longest list whose last element is smaller than x is found, copied, and x is appended. The new list replaces the old list of the same length; since the old list's last element is larger, it is no longer needed.
Table 3.15: Active lists for the 16-element sequence. Each row shows the longest list and the number of lists after the element is processed.
xEventNumber of listsLongest active list
0first list [0]10
8larger than all: extend20, 8
4extends [0] → [0, 4]; [0, 8] is redundant20, 4
12larger than all: extend30, 4, 12
2extends [0] → [0, 2]; [0, 4] is redundant30, 4, 12
10extends [0, 2] → [0, 2, 10]; [0, 4, 12] is redundant30, 2, 10
6extends [0, 2] → [0, 2, 6]; [0, 2, 10] is redundant30, 2, 6
14larger than all: extend40, 2, 6, 14
1extends [0] → [0, 1]; [0, 2] is redundant40, 2, 6, 14
9extends [0, 2, 6] → [0, 2, 6, 9]; [0, 2, 6, 14] is redundant40, 2, 6, 9
5extends [0, 1] → [0, 1, 5]; [0, 2, 6] is redundant40, 2, 6, 9
13larger than all: extend50, 2, 6, 9, 13
3extends [0, 1] → [0, 1, 3]; [0, 1, 5] is redundant50, 2, 6, 9, 13
11extends [0, 2, 6, 9] → [0, 2, 6, 9, 11]; [0, 2, 6, 9, 13] is redundant50, 2, 6, 9, 11
7extends [0, 1, 3] → [0, 1, 3, 7]; [0, 2, 6, 9] is redundant50, 2, 6, 9, 11
15larger than all: extend60, 2, 6, 9, 11, 15
0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,1500, 10, 1, 30, 1, 3, 70, 2, 6, 9, 110, 2, 6, 9, 11, 15← longest increasing subsequence
Figure 3.21: The six active lists when the sequence ends. The longest is 0, 2, 6, 9, 11, 15; the LIS length is 6.

When the sequence ends, the number of lists is the LIS length and the longest active list is an LIS. The correctness of the method rests on the following invariant.

Theorem 3.1 (The ends are increasing)

After every step, the last element of the active list of length k is strictly smaller than the last element of the active list of length k + 1.

The first k elements of the active list of length k + 1 form an increasing list of length k, and its last element is smaller than the last element of the (k + 1)-list. The active list of length k is the one with the smallest last element among lists of that length; its last element cannot exceed this element. Hence the last element of the k-list is less than or equal to the second-to-last element of the (k + 1)-list, which is strictly smaller than the last element of the (k + 1)-list. □

The theorem has two important consequences. First, which list the new element extends can be found by searching a sorted array: the array of last elements is increasing, and the place sought is the first list whose last element is greater than or equal to x. Binary search finds it in O(log n) time. Second, there is no need to store the lists themselves; storing only their last elements is enough.

3.6.5The O(n log n) code

The code below stores only the last elements of the active lists. tail[k] is the smallest last element among increasing subsequences of length k + 1. tail[0..len − 1] is always increasing; initially len = 0.

static int lisFast(int[] a) {
  int[] tail = new int[a.length];
  int len = 0;               // number of active lists
  for (int x : a) {
    int lo = 0, hi = len;    // first place with tail[lo] >= x
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (tail[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tail[lo] = x;            // replace / extend
    if (lo == len) len++;
  }
  return len;
}

For each x, the while loop finds by binary search the first position satisfying tail[lo] >= x. The search range [lo, hi) is half-open; hi is initially len. If tail[mid] < x, the place sought is to the right of mid; otherwise mid may also be a candidate and the range is narrowed to the left. When the loop ends, lo is the place where x is to be written. If lo == len, x is larger than all last elements and the number of lists grows; otherwise x takes the place of a larger last element. This latter case is the third rule of the active-lists method: the list of the same length now ends with a smaller number.

Table 3.16: Trace of lisFast({5, 2, 8, 6, 3, 6, 9, 7}); "cmp." is the number of comparisons in the binary search.
xlocmp.Actionlentail[0..len − 1]
500list empty; grows15
2012 replaces 512
811larger than all; grows22, 8
6126 replaces 822, 6
3123 replaces 622, 3
621larger than all; grows32, 3, 6
932larger than all; grows42, 3, 6, 9
7327 replaces 942, 3, 6, 7
atail5021826334659677203162734567len = 4
Figure 3.22: The end of the trace: len = 4, tail = [2, 3, 6, 7].

The method returns 4, the same result as the O(n²) algorithm. For each element the binary search makes at most ⌈log₂(len + 1)⌉ comparisons. The total time is O(n log n) and the extra memory is O(n). On an array of one million elements the O(n²) algorithm makes about 5 · 10¹¹ comparisons, while this method finishes with around twenty million comparisons.

One must be careful about the contents of the tail array. It need not be an LIS. In the 16-element example, when the process ends tail = [0, 1, 3, 7, 11, 15]. The length is correct (6), but these numbers do not occur in the sequence in this order: 7 is at position 14, while 11 is at position 13, that is, before 7. If the sequence itself is needed, whenever an element is written into tail, the index of the element at the position to its left (lo − 1) is stored as its predecessor index; the traceback is done as in the O(n²) version.

Common mistake

In the binary search, tail[mid] <= x is written instead of tail[mid] < x. Then an equal element is written not in place of the equal last element but to its right, and the list grows. The algorithm now finds the longest non-decreasing (equality allowed) subsequence rather than the strictly increasing one. For {2, 2, 2} the correct answer is 1; the faulty code answers 3.

3.7Longest common substring

3.7.1Problem and recurrence

Two strings are given. What is the longest piece that occurs contiguously in both? This problem is called the longest common substring. In plagiarism detection the longest passage that is identical in two texts, and in version comparison the common block of two files, are found with this question.

As an example take the strings "abdca" and "cbda". Their common substrings are "a", "b", "d", "c", and "bd". The longest is "bd", with length 2.

XabdcaYcbda"bd": contiguouslength 2
Figure 3.23: The longest common substring of "abdca" and "cbda" is "bd".

The brute-force method searches for every substring of the first string in the second string. A string of length m has O(m²) substrings; if each is searched for in a string of length n, the time is O(m² · n) or worse. DP answers the same question in O(m · n) time.

The choice of state is similar to that of LIS. The place where the common piece ends must be fixed. Let the strings be X (length m, the columns of the table) and Y (length n, the rows of the table).

Definition 3.11

L[i][j] is the length of the longest common piece that ends exactly at the end of the first i characters of Y and the first j characters of X.

if Y[i − 1] = X[j − 1]:   L[i][j] = L[i − 1][j − 1] + 1
otherwise:   L[i][j] = 0

Row 0 and column 0 are zero. The answer is the largest value in the table.

If the two characters are equal, the common piece ending at the previous characters grows by one character: this means adding 1 to the diagonal cell. If the characters differ, there is no common piece ending at these two positions; contiguity is broken and the counter is reset to zero. The answer is not the last cell, because the common piece can end anywhere in the strings.

3.7.2Filling the table

Let the columns be X = "abdca" and the rows Y = "cbda". The table is 5 × 6 and is filled row by row.

Table 3.17: The longest common substring table; columns X = "abdca", rows Y = "cbda".
j = 01 (a)2 (b)3 (d)4 (c)5 (a)
i = 0000000
1 (c)000010
2 (b)001000
3 (d)000200
4 (a)010001

Most of the table is zero; only the cells where matching characters intersect are filled. In row 1, 'c' matches only X[3] = 'c': L[1][4] = L[0][3] + 1 = 1. In row 2, 'b' matches X[1]: L[2][2] = 1. In row 3, 'd' matches X[2] and extends the L[2][2] = 1 on its diagonal: L[3][3] = 2. This is the common piece that starts with "b" and ends with "d". In row 4, 'a' matches in two places. L[4][1] = L[3][0] + 1 = 1. L[4][5] = L[3][4] + 1 = 0 + 1 = 1; since 'd' and 'c' on the diagonal do not match, the piece does not grow.

abdca0000000c1000010b2001000d3000200a4010001012345
Figure 3.24: The largest value is L[3][3] = 2; going 2 steps back along the diagonal gives X[1..2] = "bd". The last cell L[4][5] = 1 is not the answer.

The piece itself is read from the largest cell. The largest value is L[3][3] = 2; the piece ends at the 3rd character of X and has length 2. So the piece is X[1..2] = "bd". No separate walk backwards is needed here: the end position and the length determine the piece on their own.

3.7.3Code

The slides give only the recurrence and the table for this problem. The code below translates the same recurrence into Java. The code tracks the largest value and its end position in X while the table is filled; at the end it returns the piece with substring.

String longestCommonSubstring(String x, String y) {
  int m = x.length(), n = y.length();
  int[][] L = new int[n + 1][m + 1];
  int best = 0, end = 0;            // end: where the piece ends in X
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (y.charAt(i - 1) == x.charAt(j - 1)) {
        L[i][j] = L[i - 1][j - 1] + 1;
        if (L[i][j] > best) { best = L[i][j]; end = j; }
      }                                // on a mismatch L[i][j] stays 0
  return x.substring(end - best, end);
}

Nothing is written to mismatching cells; Java's initial value 0 stays there. The condition L[i][j] > best is a strict greater-than; if another piece of equal length is found, the first one found is kept. For "abdca" and "cbda" the method returns "bd", and for "ababc" and "babca" it returns "babc". The time and memory are O(m · n). Since each cell depends only on the cell on its diagonal, the memory can be reduced to two rows, hence to O(min(m, n)).

Common mistake

The answer is read from the last cell. The last cell is the length of the common piece that ends at the end of both strings. In the example L[4][5] = 1, but the answer is 2. For the common substring, the answer is the largest value of the table.

3.8Longest common subsequence

3.8.1Problem and recurrence

When the contiguity requirement is removed, the problem changes. We look for the longest sequence that occurs in both sequences in the same relative order; the characters in between may be skipped. This problem is called the longest common subsequence (LCS). diff and git find the unchanged lines of two files with LCS; the changed lines are those left outside the LCS. The similarity of DNA sequences and plagiarism detection are also applications of LCS.

For "abdca" and "cbda" the LCS is "bda" with length 3; the common substring had only 2. Another example: the LCS of "AGGTAB" and "GXTXAYB" is "GTAB", with length 4. "GTAB" is a subsequence of both strings but a substring of neither. The LCS need not be unique; its length is. The sequences "ABCBDAB" and "BDCABA" have three different LCSs: "BCBA", "BDAB", and "BCAB".

The recurrence is found by looking at the last characters of the two sequences. The state is defined in the same form as for the common substring, but its meaning is different: L[i][j] is the LCS length of the first i characters of Y and the first j characters of X. This time the piece need not end at the end.

Theorem 3.2 (Optimal substructure of LCS)

if Y[i − 1] = X[j − 1]:   L[i][j] = L[i − 1][j − 1] + 1
otherwise:   L[i][j] = max( L[i − 1][j],   L[i][j − 1] )

Row 0 and column 0 are zero; the answer is the last cell L[n][m].

Let the last characters be equal; call this character c. Any common subsequence that does not end with c can be extended by appending c. Hence an LCS ends with c, and the part before c is a common subsequence of the two sequences with their last characters removed. If this part could be longer, the LCS would be longer too; so it is itself an LCS: L[i − 1][j − 1] + 1. If the last characters differ, a common subsequence does not use at least one of these two characters; that character can be dropped. If the dropped character is Y's, the answer is L[i − 1][j]; if it is X's, it is L[i][j − 1]. Since we do not know which one to drop, the larger is taken. □

The recurrences of the two problems differ only in the mismatch case. Table 3.18 summarizes the differences.

Table 3.18: Comparison of the recurrences of the common substring and the common subsequence (LCS).
MatchMismatchAnswer
Common substringdiagonal + 10largest value of the table
Common subsequence (LCS)diagonal + 1max(up, left)last cell

The difference in the mismatch case reflects the essence of the two problems. In the common substring, a mismatching character breaks the chain; the counter is reset. In LCS, a mismatching character is merely skipped; the common subsequence found so far is not lost and is carried over from above or from the left. Hence the values of the LCS table never decrease going right and down; the last cell is the largest value.

3.8.2Code and trace

static int lcs(String x, String y) {
  int m = x.length(), n = y.length();
  int[][] L = new int[n + 1][m + 1];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (y.charAt(i - 1) == x.charAt(j - 1))
        L[i][j] = L[i - 1][j - 1] + 1;
      else
        L[i][j] = Math.max(L[i - 1][j],
                           L[i][j - 1]);
  return L[n][m];
}

The code applies the recurrence with two nested loops. The characters of the strings are accessed with charAt(i - 1) and charAt(j - 1), because row i of the table represents the i-th character of Y, that is, the character with 0-based index i − 1. For the same "abdca" and "cbda" example, the table fills as follows:

Table 3.19: The LCS table; columns X = "abdca", rows Y = "cbda". Bold cells are matches.
j = 01 (a)2 (b)3 (d)4 (c)5 (a)
i = 0000000
1 (c)000011
2 (b)001111
3 (d)001222
4 (a)011223

The computation of some cells is as follows. L[1][5]: 'c' ≠ 'a'; up is 0, left is 1; the value is 1. The common subsequence found by the character 'c' has been carried to the right. L[3][3]: 'd' = 'd'; 1 is added to the diagonal L[2][2] = 1 and it becomes 2 ("bd"). L[4][3]: 'a' ≠ 'd'; up is 2, left is 1; the value is 2. L[4][5]: 'a' = 'a'; 1 is added to the diagonal L[3][4] = 2: 3. In the common substring table this diagonal cell was 0; in LCS, "bd" had been carried to the right and was 2. Once the contiguity requirement is lifted, 'a' can be appended to the end of "bd".

abdca0000000c1000011b2001111d3001222a4011223012345
Figure 3.25: The table is filled: L[4][5] = 3. 20 cells were computed, each in O(1).

The time and memory are O(m · n). If only the length is needed, two rows suffice and the memory drops to O(min(m, n)). If the sequence itself is also wanted, the whole table must be kept.

3.8.3Reconstruction

The LCS itself is read back starting from the last cell. At each cell we look at which branch of the recurrence was used:

  • If the characters are equal, the character is added to the LCS and we move to the diagonal cell.
  • If they are not equal, we go in the direction the value came from: left if the left cell is larger than the one above, up otherwise.
  • We stop when we reach row 0 or column 0. Since the characters are found from last to first, the result is reversed.
Table 3.20: LCS traceback for "abdca" and "cbda".
CellCharactersDecisionFound (from the end)
L[4][5] = 3'a' = 'a'append, diagonala
L[3][4] = 2'd' ≠ 'c'left (2) > up (1): go lefta
L[3][3] = 2'd' = 'd'append, diagonalda
L[2][2] = 1'b' = 'b'append, diagonalbda
L[1][1] = 0'c' ≠ 'a'up (0) ≥ left (0): go upbda
L[0][1]—boundary; stopbda
abdca0000000c1000011b2001111d3001222a4011223012345
Figure 3.26: The traceback path. The green cells are matches: LCS = "bda", length 3. The traceback takes O(m + n) steps.

At each step either the row, the column, or both decrease by one; the traceback takes at most m + n steps. The following method fills the table and returns the LCS itself.

String lcsString(String x, String y) {
  int m = x.length(), n = y.length();
  int[][] L = new int[n + 1][m + 1];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      L[i][j] = y.charAt(i - 1) == x.charAt(j - 1) ? L[i - 1][j - 1] + 1
              : Math.max(L[i - 1][j], L[i][j - 1]);
  StringBuilder sb = new StringBuilder();
  int i = n, j = m;
  while (i > 0 && j > 0)
    if (y.charAt(i - 1) == x.charAt(j - 1)) {   // match: diagonal
      sb.append(x.charAt(j - 1)); i--; j--;
    } else if (L[i][j - 1] > L[i - 1][j]) j--;  // left larger: go left
    else i--;                                   // otherwise: go up
  return sb.reverse().toString();
}

The method returns "bda" for "abdca" and "cbda", and "GTAB" for "AGGTAB" and "GXTXAYB". The rule of going up on a tie determines which LCS is found when there are several. For "ABCBDAB" (columns) and "BDCABA" (rows), the method finds "BDAB"; if the rule is changed so that ties go left, a different LCS may be found.

3.8.4A DNA example

In bioinformatics, how similar two DNA sequences are can be measured by the length of their LCS. The sequences in Figure 3.27 are ACCGGTGGACAATTCA and GGAAAGAGATATGCAC. Both consist of 16 bases.

ACCGGTGGACAATTCAGGAAAGAGATATGCAC
Figure 3.27: Two DNA sequences and an LCS: GGAAATTCA, length 9. The lines joining matched bases do not cross.

The lines in the figure are the visual counterpart of a common subsequence. The lines joining matched characters do not cross, because the relative order is kept in both sequences. Every matching built with non-crossing lines is a common subsequence. The LCS is the matching with the most lines that can be drawn this way. The DP result is GGAAATTCA, of length 9. If the sequences are swapped, the traceback may find a different LCS such as GGGGAATCA; the length is still 9.

Matching by eye is misleading. For example, AAAATTCA is also a valid common subsequence: in the first sequence the A's are at positions 0, 8, 10, and 11, followed by T, T, C, A; the same order is found in the second sequence. But its length is 8 and it is not the longest. Only the DP table, which implicitly tries all options, gives the right answer. A 16 × 16 table finishes this job with 256 cells; trying all possible subsequences would mean searching 2¹⁶ = 65,536 subsequences in the other sequence.

3.9Other classic DP problems

The problems studied in these notes follow a pattern: the state is defined by a few integers, the recurrence tries the options of the last decision, and the table is filled in a suitable order. The same pattern solves many other classic problems. Table 3.21 summarizes seven of them; then four are worked through with small examples.

Table 3.21: Other classic dynamic programming problems.
ProblemState and recurrenceTime
Edit distanceD[i][j] = min(D[i−1][j] + 1, D[i][j−1] + 1, D[i−1][j−1] + [aᵢ ≠ bⱼ]); D[i][0] = i, D[0][j] = jO(m · n)
Coin changefewest coins: P[x] = 1 + min P[x − c] (c ≤ x); P[0] = 0O(k · X)
Maximum subarrayV(i) = max(a[i], V(i−1) + a[i]) (Kadane); answer max V(i)O(n)
Matrix-chain multiplicationM[i][j] = min { M[i][k] + M[k+1][j] + pᵢ₋₁ · pₖ · pⱼ : i ≤ k < j }O(n³)
Traveling salesman (Held–Karp)dp[S][i]: shortest path that visits the set S and ends at i; dp[S][i] = min dp[S − i][j] + d(j, i)O(n² · 2ⁿ)
Bellman–Forddₖ(v): shortest path with at most k edges; dₖ(v) = min(dₖ₋₁(v), dₖ₋₁(u) + w(u, v))O(V · E)
Optimal binary search treee[i][j] = min { e[i][r−1] + e[r+1][j] : i ≤ r ≤ j } + w(i, j)O(n³)

3.9.1Edit distance

The edit distance (Levenshtein distance) between two strings is the smallest number of single-character operations needed to turn one into the other. There are three kinds of operations: deleting a character, inserting a character, and replacing a character with another one. A spell checker suggests dictionary words whose distance to a misspelled word is small.

D[i][j] is the minimum cost of turning the first i characters of a into the first j characters of b. There are three options for the last character. The last character of a is deleted: D[i − 1][j] + 1. The last character of b is inserted: D[i][j − 1] + 1. The last characters are matched: free if they are equal, otherwise with one replacement, D[i − 1][j − 1] + [aᵢ ≠ bⱼ]. The square brackets mean 1 if the condition is true and 0 if it is false. The base cases are clear: from the empty string to a string of j characters takes j insertions, and from a string of i characters to the empty string takes i deletions.

int editDistance(String a, String b) {
  int m = a.length(), n = b.length();
  int[][] D = new int[m + 1][n + 1];
  for (int i = 0; i <= m; i++) D[i][0] = i;     // i deletions
  for (int j = 0; j <= n; j++) D[0][j] = j;     // j insertions
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++) {
      int diff = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
      D[i][j] = Math.min(Math.min(D[i - 1][j] + 1,   // delete
                                  D[i][j - 1] + 1),  // insert
                         D[i - 1][j - 1] + diff);    // replace / same
    }
  return D[m][n];
}
Example 3.7

What is the edit distance between "kitap" and "kayak"?

""kayak
""012345
k101234
i211234
t322234
a432323
p543333

The result is D[5][5] = 3. Reading along the diagonal, the characters k and a match; i → a, t → y, and p → k are replaced. For example D[2][2]: 'i' ≠ 'a'; the options are D[1][2] + 1 = 2, D[2][1] + 1 = 2, and D[1][1] + 1 = 1; the smallest is 1. D[4][4]: 'a' = 'a'; the diagonal D[3][3] = 2 is carried over for free.

Edit distance is closely related to LCS. If only insertion and deletion are allowed, the minimum number of operations is m + n − 2 · LCS: the characters not in the LCS are deleted from one string and inserted into the other.

3.9.2Coin change

Let the coin denominations be c₁, …, cₖ and an amount X be given. This problem has two famous questions: what is the fewest number of coins that pay the amount, and in how many different ways can it be paid? Since there is an unlimited supply of each coin, both are relatives of unbounded knapsack.

Fewest coins. P[x] is the fewest number of coins needed to pay the amount x. If the last coin given is c, then x − c remains: P[x] = 1 + min P[x − c] (c ≤ x), P[0] = 0. Small amounts must be ready first; x is filled from 1 to X. The table has X + 1 cells, and k coins are tried in each cell: O(k · X) time, O(X) memory. This too is a pseudo-polynomial time.

int minCoins(int[] coins, int X) {
  int[] P = new int[X + 1];            // P[0] = 0
  for (int x = 1; x <= X; x++) {
    P[x] = Integer.MAX_VALUE;
    for (int c : coins)
      if (c <= x && P[x - c] != Integer.MAX_VALUE)
        P[x] = Math.min(P[x], P[x - c] + 1);
  }
  return P[X];                         // MAX_VALUE: cannot be paid
}

long countWays(int[] coins, int X) {
  long[] d = new long[X + 1];
  d[0] = 1;                            // the only way to pay 0: no coins
  for (int c : coins)                   // outer loop over coins
    for (int x = c; x <= X; x++)
      d[x] += d[x - c];
  return d[X];
}
Example 3.8

Coins {1, 3, 4}, amount 6. How many coins are needed at least? How many does the greedy method use?

Table: P = [0, 1, 2, 1, 1, 2, 2]. For example P[5] = 1 + min(P[4], P[2], P[1]) = 1 + 1 = 2 (4 + 1). Last cell: P[6] = 1 + min(P[5], P[3], P[2]) = 1 + min(2, 1, 2) = 2; the payment is 3 + 3. The greedy method first takes the largest coin: 4, then 1, then 1. It uses three coins and is not optimal. In most currency systems used every day the greedy method gives the right result, but this is not true for every currency system.

Number of ways. d[x] is the number of different ways to pay the amount x; d[0] = 1 (giving no coins). Here the order of the loops is decisive. If the outer loop is over coins and the inner loop over amounts, each way is counted once: coins are added in a fixed order, and "2 + 1" and "1 + 2" are considered the same. If the loops are swapped, ordered sequences are counted. For {1, 2, 5} and the amount 5, the correct answer is 4: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, and 1 + 1 + 1 + 1 + 1. With the loops reversed, the result would be 9.

Common mistake

It is assumed that the greedy choice is always right in coin change. {1, 3, 4} with amount 6 is a counterexample: greedy gives 3 coins, DP gives 2. As in knapsack, unless the correctness of the greedy choice is proved separately, DP is needed.

3.9.3Maximum subarray

We look for the contiguous piece of an array with the largest sum. The recurrence was written while discussing optimal substructure: V(i) = max(a[i], V(i − 1) + a[i]). At each step there are two options: extend the previous piece or restart with a[i]. If the sum of the previous piece is negative, carrying it is a loss; restarting is better. Since V(i) depends only on V(i − 1), a single variable suffices.

int kadane(int[] a) {
  int V = a[0], best = a[0];
  for (int i = 1; i < a.length; i++) {
    V = Math.max(a[i], V + a[i]);   // restart or extend
    best = Math.max(best, V);
  }
  return best;
}
Example 3.9

What is the maximum subarray of [−2, 1, −3, 4, −1, 2, 1, −5, 4]?

The V values are −2, 1, −2, 4, 3, 5, 6, 1, 5 in turn. At index 1 the previous sum is −2, so we restart: V = max(1, −1) = 1. At index 3 the previous sum is −2; we restart with 4. Then the piece grows: 4 − 1 = 3, 3 + 2 = 5, 5 + 1 = 6. The −5 lowers the piece to 1 but does not push it below zero. The largest value is 6: [4, −1, 2, 1]. The time is O(n) and the memory is O(1).

3.9.4Matrix-chain multiplication

The ordinary product of a p × q matrix and a q × r matrix requires p · q · r scalar multiplications. Matrix multiplication is associative: (AB)C = A(BC). The result is the same, but the cost can differ greatly depending on the parenthesization. The problem is to find the parenthesization that computes a chain of matrices with the fewest scalar multiplications.

Let matrix Aᵢ have size pᵢ₋₁ × pᵢ. M[i][j] is the minimum cost of the chain Aᵢ … Aⱼ. The last multiplication of this chain splits it in two at some point k: first Aᵢ … Aₖ and Aₖ₊₁ … Aⱼ are computed, then the two results of sizes pᵢ₋₁ × pₖ and pₖ × pⱼ are multiplied. All values of k are tried. Here the states are filled by chain length: short chains must be ready first.

long matrixChain(int[] p) {          // matrix A_i is p[i-1] × p[i]
  int n = p.length - 1;
  long[][] M = new long[n + 1][n + 1];
  for (int len = 2; len <= n; len++)      // chain length
    for (int i = 1; i + len - 1 <= n; i++) {
      int j = i + len - 1;
      M[i][j] = Long.MAX_VALUE;
      for (int k = i; k < j; k++)
        M[i][j] = Math.min(M[i][j],
            M[i][k] + M[k + 1][j] + (long) p[i - 1] * p[k] * p[j]);
    }
  return M[1][n];
}
Example 3.10

A₁ is 10 × 30, A₂ is 30 × 5, and A₃ is 5 × 60 (p = 10, 30, 5, 60). Which is the best parenthesization?

(A₁A₂)A₃: 10 · 30 · 5 + 10 · 5 · 60 = 1500 + 3000 = 4500 multiplications. A₁(A₂A₃): 30 · 5 · 60 + 10 · 30 · 60 = 9000 + 18,000 = 27,000 multiplications. The first is six times cheaper; the method returns 4500.

The number of states is O(n²) (the pairs i ≤ j); in each state O(n) split points are tried. The time is O(n³). Trying every parenthesization one by one would mean as many options as the Catalan numbers: 4862 for 10 matrices and more than 1.7 billion for 20 matrices.

3.9.5Traveling salesman, Bellman–Ford, and optimal binary search trees

The last three problems in the table show that a state can take different forms: a set and a vertex, a vertex and an edge count, a range of keys.

  • Traveling salesman (Held–Karp). The state is a set and a vertex: dp[S][i] is the shortest path that starts at the origin, visits all vertices of the set S, and ends at i. The set is stored as a bit mask. There are 2ⁿ · n states, and each tries O(n) predecessors: O(n² · 2ⁿ). This time is still exponential, but much smaller than the (n − 1)! of trying every tour. For 20 vertices, 20² · 2²⁰ ≈ 4.2 · 10⁸ against 19! ≈ 1.2 · 10¹⁷.
  • Bellman–Ford. The state is a vertex and an edge count: dₖ(v) is the shortest path using at most k edges. In each round all edges are relaxed; V − 1 rounds suffice. The table is reduced to one dimension and the time is O(V · E).
  • Optimal binary search tree. If the access probabilities of the keys are known, we look for the tree with the smallest expected search cost. The state is a range of keys; the recurrence tries every root choice for the range. The structure is the same as in matrix-chain multiplication and the time is O(n³).

3.10Common mistakes

Dynamic programming mistakes usually do not produce a compile error. The code runs, returns a number, and the number is wrong. The mistakes below, together with the list in the slides, collect those met throughout these notes.

Common mistake

Forgetting the base cases. If K[0][c], dp[i][0], or fib(0) and fib(1) are initialized wrongly, the whole table shifts. In subset sum, if column 0 is not made true, every answer is "no"; in coin change, if infinity is written instead of P[0] = 0, no amount can be paid.

Common mistake

Index shift. The table has size n + 1 but the array has n elements: row i uses v[i - 1], and row i of the LCS table uses charAt(i - 1). Writing v[i] shifts every row to the next element and runs out of the array in the last row.

Common mistake

Wrong loop direction. In one-dimensional 0/1 knapsack, scanning the capacity from small to large takes an item more than once; the result becomes the answer of unbounded knapsack. For the number of ways in coin change, putting the outer loop over amounts counts different orders of the same payment separately.

Common mistake

Confusing substring with subsequence. In the common substring, a mismatch writes 0 and the answer is the largest value of the table. In LCS, a mismatch writes max(up, left) and the answer is the last cell. In LIS too, the answer is not the last cell but the largest dp[i].

Common mistake

Assuming the greedy choice is enough. In 0/1 knapsack (the 60, 100, 120 ₺ example) and in coin change ({1, 3, 4} with 6) the greedy choice is not optimal. The greedy method is used only if its correctness has been proved.

Common mistake

Taking O(n · W) to be polynomial. W is a numeric value; the input size is log W bits. For large W the table cannot be built.

Common mistake

Choosing the wrong "not computed" marker in the cache. In an int table, 0 means both "empty" and "answer 0"; states whose answer is 0 are recomputed every time. Integer with null, or a table filled with −1, avoids this confusion.

Common mistake

Losing the traceback while saving memory. A one-dimensional table gives the optimal value, but the rows needed to read the choices back have been deleted. If the choices are wanted too, either the whole table or a separate decision table is kept.

3.11Summary

  • Dynamic programming = overlapping subproblems + optimal substructure. Each subproblem is solved once and its result is stored in a table.
  • Design steps: the structure of an optimal solution, the state and recurrence (with base cases), the order of computation, the table size, filling the table, and reconstructing the solution.
  • Total time ≈ number of states × work per state. This rule explains every complexity in these notes.
  • Memoization works top-down and solves only the states that are needed; tabulation works bottom-up, has no call overhead, and lends itself to memory reduction. Their asymptotic times are the same.
  • A greedy approach looks at a single option at each step; it is correct only if the greedy-choice property has been proved. In divide and conquer the subproblems are independent and no table is needed.
Table 3.22: Summary of the problems studied in these notes.
ProblemState / recurrenceTime · memory
FibonacciF(n) = F(n−1) + F(n−2); memoization or tableO(n) · O(1)
0/1 knapsackK[i][c] = max(K[i−1][c], vᵢ + K[i−1][c−wᵢ])O(nW) · O(W)
Unbounded knapsackdp[i][c] = max(dp[i−1][c], pᵢ + dp[i][c−wᵢ])O(nW) · O(W)
Subset sumdp[i][j] = dp[i−1][j] ∨ dp[i−1][j−aᵢ]O(n · target)
LISdp[i] = 1 + max dp[j] (j < i, a[j] < a[i]); or active listsO(n²) / O(n log n)
Longest common substringif equal, diagonal + 1, otherwise 0; answer is the largest value in the tableO(mn)
LCSif equal, diagonal + 1, otherwise max(up, left); answer is the last cellO(mn)
  • 0/1 knapsack, subset sum, and coin change are pseudo-polynomial: the time depends on the value of a number in the input, not on its bit length.
  • In a one-dimensional table the loop direction determines the problem: large to small gives 0/1, small to large gives unbounded.
  • The solution itself is read back from the table: the rows where the value changes in knapsack, the diagonal steps in LCS, the chain of predecessor indices in LIS.

3.12Key terms

  • dynamic programming (DP)
  • subproblem
  • overlapping subproblems
  • optimal substructure
  • memoization
  • tabulation
  • top-down / bottom-up
  • traceback
  • greedy-choice property
  • 0/1 knapsack
  • fractional knapsack
  • unbounded knapsack
  • pseudo-polynomial
  • subset sum
  • longest increasing subsequence (LIS)
  • longest common substring
  • longest common subsequence (LCS)
  • edit distance
  • coin change
  • matrix chain multiplication

3.13Test Yourself

Questions 2 and 3 use the same items: (value, weight) = (12, 2), (17, 3), (30, 5); capacity 6.

  1. In a plain recursive call of fib(6), how many times is fib(2) called? With memoization, how many times is fib(2) computed, and what is the total number of calls?

    Answer

    In the tree of fib(n), fib(k) is called F(n − k + 1) times: for fib(2), F(5) = 5 times. Plain recursion makes 2 · F(7) − 1 = 25 calls in total. With memoization fib(2) is computed once and its second call returns from the table; the total number of calls is 2 · 6 − 1 = 11.

  2. What is the last row of the 0/1 knapsack table? What is the maximum value, and which items are chosen?

    Answer

    The rows are: [0, 0, 12, 12, 12, 12, 12], [0, 0, 12, 17, 17, 29, 29], [0, 0, 12, 17, 17, 30, 30]. The answer is K[3][6] = 30. Traceback: 30 ≠ K[2][6] = 29, so item 3 is taken and c = 1; no other item fits into 1 kg. Only the item worth 30 is chosen. 12 + 17 = 29 falls short by one.

  3. What would the answer be if any number of copies of the same items could be taken? What number would be returned if the inner loop of the one-dimensional 0/1 code were written from small to large?

    Answer

    Unbounded: dp = [0, 0, 12, 17, 24, 30, 36]; the answer is 36, three items worth 12 (2 kg). The one-dimensional 0/1 code scanned from small to large also returns 36, because that code now solves the unbounded knapsack.

  4. In the 0/1 knapsack DP, how does the running time change if W doubles? What happens if one bit is added to the binary representation of W?

    Answer

    In both cases the table width roughly doubles, and so does the running time. A one-bit increase grows the input size by only one bit, yet the running time doubles. For a b-bit W the time is O(n · 2ᵇ); this is what pseudo-polynomial means.

  5. Does the set {2, 3, 7, 8, 10} have a subset with sum 11? Which sums are reachable in the last row of the table?

    Answer

    Yes: {3, 8}; this is the only solution. The reachable sums in the last row are 0, 2, 3, 5, 7, 8, 9, 10, and 11 (1, 4, and 6 cannot be obtained). The traceback starts at dp[5][11]: since 11 can be formed without 10, 10 is not chosen; 8 is chosen (j = 3); 7 is not chosen; 3 is chosen (j = 0).

  6. For the array [3, 10, 2, 1, 20, 4, 6, 7], what is the dp array of the O(n²) algorithm? What is the tail array when lisFast finishes?

    Answer

    dp = [1, 2, 1, 1, 3, 2, 3, 4]; the LIS length is 4, for example 3, 4, 6, 7. tail goes through [3], [3, 10], [2, 10], [1, 10], [1, 10, 20], [1, 4, 20], [1, 4, 6], [1, 4, 6, 7] in turn. In this example the final array is an LIS (1, 4, 6, 7), but that is a coincidence; the array need not be an LIS.

  7. What are the longest common substring and LCS lengths for "kalem" and "kelam"?

    Answer

    The common substring has length 1: none of the two-letter pieces (ka, al, le, em versus ke, el, la, am) is shared. The LCS has length 3; "kam", "kem", and "klm" are three different LCSs. Lifting the contiguity requirement triples the length.

  8. What is the edit distance between "kedi" and "kadın"?

    Answer

    It is 3: e → a and i → ı are replaced, and n is appended. The last row of the table is [4, 3, 3, 2, 2, 3]; D[4][5] = 3.

  9. Coins {1, 5, 6, 9}, amount 11. How many coins are needed at least? How many does the greedy method use?

    Answer

    DP: 2 coins (5 + 6). Greedy: 9 + 1 + 1, 3 coins. In this currency system too, the greedy choice is not optimal.

  10. A₁ is 5 × 10, A₂ is 10 × 3, and A₃ is 3 × 12. What is the fewest number of scalar multiplications needed?

    Answer

    (A₁A₂)A₃ = 5 · 10 · 3 + 5 · 3 · 12 = 150 + 180 = 330. A₁(A₂A₃) = 10 · 3 · 12 + 5 · 10 · 12 = 360 + 600 = 960. The minimum is 330.

3.14Further reading

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 14: presents the principles of DP, with proofs, through rod cutting, matrix-chain multiplication, LCS, and optimal binary search trees.
  • J. Kleinberg and É. Tardos, Algorithm Design (2005), Chapter 6: discusses the choice of state step by step through weighted interval scheduling, knapsack, sequence alignment, and Bellman–Ford.
  • S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms (2006), Chapter 6: interprets DP as shortest paths in a directed acyclic graph; treats LIS, edit distance, knapsack, and the traveling salesman problem briefly and clearly.
  • R. Bellman, Dynamic Programming (1957): the first comprehensive account of the method and the principle of optimality.

3.15References

  1. R. Bellman, Dynamic Programming, Princeton University Press, 1957.
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 14: Dynamic Programming).
  3. S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2006 (Chapter 6).
  4. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2005 (Chapter 6).

Related pages: Chapter 3 slides · © Sercan Külcü. All rights reserved.