13. Dynamic programming

Dynamic programming (DP) is a way of solving a problem by breaking it into smaller subproblems, computing each subproblem exactly once, and storing its answer to be reused.

Two conditions a problem must meet to be solvable with DP:

1. Overlapping subproblems. The same subproblem appears many times — like fib(43), which was computed hundreds of millions of times in Chapter 06.
2. Optimal substructure. The best answer to the large problem is built from the best answers to its subproblems.

The shortest way to remember what DP is:

DP = brute force − repeated work.

Chapter 06 already showed the difference in numbers. fib(45) written as plain recursion needs 3,672,623,805 calls, even though there are only 46 truly distinct answers: fib(0) through fib(45). The rest is recomputation. Once every answer is stored, the work drops from billions to dozens of steps — and that is the whole idea of DP.

Two writing styles

Top-down (memoization). Write ordinary recursion, then add memory. You already did this in the Chapter 06 challenge.

long long ingat[100];

long long fib(int n) {
    if (n <= 1) return n;
    if (ingat[n] != -1) return ingat[n];
    return ingat[n] = fib(n - 1) + fib(n - 2);
}

Bottom-up (tabulation). Fill a table from the smallest subproblem to the largest, without recursion.

long long dp[100];

dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];

Both compute the same thing:

Top-down is easier to write from existing recursion; bottom-up is faster and has no risk of running out of stack memory. This book uses bottom-up for the following examples.

Five steps to build a DP

Every time you face a DP problem, answer these five questions on paper before writing code:

1. What is the state? What does dp[i] mean? Write it as a complete sentence.
2. What is the base case? The smallest state whose answer is already known.
3. What is the transition? How dp[i] is computed from smaller states.
4. What is the fill order? Every state that is used must already be filled.
5. Which state holds the answer?

Step 1 is the hardest, and the rest usually follows.

Example 1: climbing stairs

There is a staircase with n steps. Each move goes up 1 or 2 steps. How many different ways are there to reach step n?

1. State. dp[i] = the number of ways to reach step i.
2. Base case. dp[0] = 1 (one way: stay at the bottom), dp[1] = 1.
3. Transition. To arrive at i, the last move comes from i − 1 or from i − 2. So dp[i] = dp[i-1] + dp[i-2].
4. Order. From small to large.
5. Answer. dp[n].

dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
cout << dp[n] << "\n";

Filling the table for n = 6:

Check by hand for i = 3: there are three ways to reach step 3, namely 1+1+1, 1+2, and 2+1. This matches dp[3] = 3.

The result is the Fibonacci sequence again — a sign that many problems that look different actually have the same state.

Example 2: fewest coins

This is the problem that made greedy fail in Chapter 12.

Given coin denominations c[1..m] and a value k. What is the fewest number of coins that make exactly k? Print -1 if it is impossible.

1. State. dp[v] = the fewest coins to make value v.
2. Base case. dp[0] = 0.
3. Transition. dp[v] = 1 + min(dp[v - c[i]]) over every coin c[i] that does not exceed v.
4. Order. v from 1 to k.
5. Answer. dp[k], or -1 if its value is still infinite.

const int BESAR = 1000000000;

dp[0] = 0;
for (int v = 1; v <= k; v++) {
    dp[v] = BESAR;
    for (int i = 0; i < m; i++) {
        if (v >= c[i] && dp[v - c[i]] + 1 < dp[v])
            dp[v] = dp[v - c[i]] + 1;
    }
}
cout << (dp[k] >= BESAR ? -1 : dp[k]) << "\n";

Filling the table for coins {1, 3, 4}:

How to read one cell: dp[6] checks three possibilities for the last coin — coin 1 gives dp[5] + 1 = 3, coin 3 gives dp[3] + 1 = 2, coin 4 gives dp[2] + 1 = 3. The smallest is 2, so dp[6] = 2.

Notice that DP does not need to know which coin "should" be taken first. It tries all of them as the last coin, then uses the subproblem answers that are already proven best. That is where it differs from greedy, which only tries one choice and never goes back.

The number of steps is k × m: one state per value, and each state checks m coins. For k = 10⁶ and m = 10 that is 10 million — fast.

Compare with greedy for {1, 3, 4} and k = 6: DP answers 2, greedy answers 3. DP checks every possibility without repeating work.

Example 3: 0/1 knapsack

There are n items; item i has weight w[i] and value v[i]. The bag can only hold weight W. Each item may be taken at most once. What is the largest value that can be carried?

1. State. dp[i][b] = the largest value using the first i items with weight limit b.

2. Base case. dp[0][b] = 0 for all b.

3. Transition. Two choices for item i:

   • not taken: dp[i-1][b]
   • taken (if b >= w[i]): dp[i-1][b - w[i]] + v[i]

   Take the larger one.

4. Order. i from 1 to n, b from 0 to W.

5. Answer. dp[n][W].

for (int i = 1; i <= n; i++) {
    for (int b = 0; b <= W; b++) {
        dp[i][b] = dp[i - 1][b];                       // not taken
        if (b >= w[i] && dp[i - 1][b - w[i]] + v[i] > dp[i][b])
            dp[i][b] = dp[i - 1][b - w[i]] + v[i];     // taken
    }
}

The number of steps is n × W. For n = 100 and W = 10,000 that is a million.

Tracing for W = 5 and three items — (weight 2, value 3), (weight 3, value 4), (weight 4, value 5). Each row is the state after item i has been considered:

The answer is dp[3][5] = 7, namely the first and second items (weight 2 + 3 = 5, value 3 + 4 = 7). Trace one cell to make sure you understand: dp[2][5] chooses between not taking the second item (dp[1][5] = 3) and taking it (dp[1][5-3] + 4 = dp[1][2] + 4 = 7). The larger one is 7.

Notice also that each row only reads the row directly above it. That property is what lets the knapsack table be compressed into a single row to save memory — a technique that is useful when n is large, but should not be used before the two-dimensional version is fully mastered.

Counting DP steps

The formula is always:

number of steps = number of states × cost of one transition

Use that formula together with the constraints table from Chapter 10: if the number of states alone is already 10¹⁰, the state needs to be redesigned.

Recognizing DP problems

Four signs that a problem is most likely DP:

1. The problem asks for the most, the fewest, or how many ways — not "print one example".
2. Each step is a choice (take or not, move 1 or 2, cut here or not).
3. A brute force that tries all choices is clearly correct, but the number of possibilities is 2ⁿ or n!.
4. The choices already made affect the rest only through a small amount of information — for example "remaining bag capacity" or "which step we have reached", not the entire history of choices.

The fourth sign is the most decisive, because that small amount of information becomes the dp state. If the rest of the problem turns out to depend on the entire history of choices, the state will explode and the problem is not a simple DP.

Comparison with the two previous approaches:

Most common mistakes

• The state is not defined as a sentence. If dp[i] cannot be explained in one sentence, the transition will certainly be a mess.
• Wrong base case. dp[0] = 0 and dp[0] = 1 are two different problems: one computes a sum, the other counts ways.
• Wrong fill order, so a state that is used has not been filled yet.
• Array too small, so the answer for the last k gets overwritten.

Homework

OSN tips

The first sign of a DP problem: "how many ways", "fewest", or "largest", with stacked choices. If every step presents several choices and the current choice affects the next ones, greedy usually fails and DP usually works.

State the state in one sentence before writing code. That sentence must have the form "dp[...] is the ... of the first ...". If the sentence cannot be written yet, the code must not be written yet. Almost all DP mistakes come from an unclear state, not from typos.

Compute the table size before creating it. The number of states multiplied by the cost per state is the number of steps, and the number of states multiplied by the type size is the memory:

If the table is too large, often only the last one or two rows are actually needed. Problem 2 below is an example.

Check the initial state separately. The most common DP mistake is not in the recurrence formula but in the initial values: dp[0] should be 1 or 0, an upper bound should be "impossible" rather than zero, and the first cell of a grid should be checked for being blocked.

The loop direction determines the meaning. In a DP that uses one array to save memory, a backward loop means "each item is used at most once", while a forward loop means "items may be used multiple times". Two different problems, two different directions, nearly identical code.

Test the DP against brute force. For N ≤ 15, the brute force answer is certainly correct. Running both on hundreds of small random inputs catches initial-state mistakes and boundary mistakes that do not show up in the sample tests.

Summary

• DP is brute force minus repeated work: every subproblem is computed exactly once and its answer is stored.
• The conditions are overlapping subproblems and optimal substructure.
• Two styles: top-down (recursion + memory) and bottom-up (filling a table). Both compute the same thing.
• Five questions answered on paper: state, base case, transition, fill order, where the answer is. The state must be writable as one complete sentence.
• Number of steps = number of states × cost of one transition; compare with the constraints table from Chapter 10 before writing code.
• Signs of a DP problem: it asks for the most/fewest/how many ways, each step is a choice, and the rest of the problem depends only on a small amount of information.

OSN-style exercises

The following three problems represent the three most common forms of DP: counting the number of paths on a grid, choosing with a restriction, and checking whether a sum can be formed.

Skeletons for all three are in exercises/13/osn/.

Problem 1 — Grid Paths with Obstacles

A map is laid out as a grid of R rows and C columns. Some cells can be passed through, some are blocked. An ant is at the top-left cell and wants to reach the bottom-right cell. From a cell, it may only move right or down, and it may not step on a blocked cell.

Count how many different paths it can take.

Input format. The first line contains two integers R and C. Each of the next R lines contains C characters: . for a passable cell and # for a blocked cell.

Output format. One line containing the number of paths. If there is no path at all, print 0.

Constraints. 1 ≤ R, C ≤ 17.

Sample input

3 3
...
.#.
...

Sample output

2

Explanation. Without obstacles there are six paths. The blocked center cell cuts off four of them, leaving two: along the top edge then the right edge, or the left edge then the bottom edge.

Skeleton: exercises/13/osn/01-jalur-grid.cpp

Problem 2 — No Neighbors

Along one side of a street stand N stalls in a row, and stall i yields a profit of Aᵢ if rented. The owner forbids two adjacent stalls from being rented by the same person.

Determine the largest total profit that can be obtained by renting a set of stalls in which no two are adjacent. Renting nothing at all is also allowed.

Input format. The first line contains an integer N. The second line contains N integers A₁ A₂ … A_N.

Output format. One line containing the largest total profit.

Constraints.

• 1 ≤ N ≤ 200,000
• 0 ≤ Aᵢ ≤ 10⁹

Sample input

6
3 2 7 10 12 5

Sample output

22

Explanation. The best choice is stalls 1, 3, and 5: 3 + 7 + 12 = 22. The choice 3 + 10 + 5 only yields 18, and 10 + 12 is not allowed because the two stalls are adjacent.

Skeleton: exercises/13/osn/02-tanpa-bertetangga.cpp

Problem 3 — Split into Two Equal Weights

The organizers have N sacks of known weight, and two identical trucks. All sacks must be loaded, and the organizers want both trucks to carry exactly the same weight. Sacks may not be split.

Determine whether such a split is possible.

Input format. The first line contains an integer N. The second line contains N integers, the weight of each sack.

Output format. One line containing YA ("yes") or TIDAK ("no").

Constraints.

• 1 ≤ N ≤ 100
• 1 ≤ weight ≤ 100

Sample input

4
1 5 11 5

Sample output

YA

Explanation. The first truck carries sacks 1, 2, and 4 with a total of 1 + 5 + 5 = 11; the second truck carries sack 3, which weighs 11. For input 1 2 5, the answer is TIDAK because the total is 8 but no subset sums to 4.

Skeleton: exercises/13/osn/03-bagi-dua.cpp

Stuck or already done? Open the homework solutions page.