13. Dynamic programming — Homework Solutions

The answer .cpp files are in exercises/13/homework/solutions/.

Open this page after trying on your own. Compare your line of reasoning with the How to think about it section, not the code line by line: two pieces of code with different shapes can both be correct, and what is worth copying is how to get there. The Test part of each problem contains inputs and outputs that have already been checked — run your own answer on those inputs before considering yourself done.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/13/homework/solutions/01-tangga.cpp
./jawab

Problem 1 — Climbing stairs by threes

Problem. The number of ways to reach step n with moves of 1, 2, or 3.

How to think about it. Five steps:

1. State. dp[i] = the number of ways to reach step i.
2. Base case. dp[0] = 1, dp[1] = 1, dp[2] = 2 (namely 1+1 and 2).
3. Transition. dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
4. Order. From small to large.
5. Answer. dp[n].

There must be three base cases, not two: the transition for i = 2 would touch dp[-1] if forced.

Walkthrough.

dp[0] = 1;
if (n >= 1) dp[1] = 1;
if (n >= 2) dp[2] = 2;

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

cout << dp[n] << "\n";

For n = 5 the answer is 13.

Tests.

The last row tests two things at once: the array is large enough for n = 10⁶, and % MOD is taken at every addition, not only at the end.

Common mistakes.

• Writing if (n >= 2) dp[2] = 2; without the n >= 1 and n >= 2 guards, then reading a dp[n] that holds garbage for small n.
• Forgetting % MOD inside the loop, so it overflows even though the answer is reduced modulo at the end.
• Using int for dp. The sum of three values close to 10⁹ exceeds the int limit before it can be reduced modulo.

Problem 2 — Fewest coins

Problem. The fewest coins to reach k, or -1.

How to think about it. The state is dp[v] = the fewest coins for value v. The initial value BESAR ("large") means "not reached yet/unreachable". The transition tries every coin as the last coin taken.

Why check all coins instead of taking the largest? Because this is the problem that made greedy fail in Chapter 12. DP tries all of them, and since each value is computed once, the cost stays low.

Walkthrough.

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";

Check: coins 1 3 4 with k = 6 give 2; coins 2 4 with k = 7 give -1 because all coins are even.

Tests.

The last two rows test the "impossible" path. What separates a correct answer from a wrong one here is the marker value BESAR: it must be large enough to never win a comparison, but dp[v - c[i]] + 1 must not overflow because of it.

Common mistakes.

• Using a BESAR that is too large, so dp[v - c[i]] + 1 overflows. One billion is safe for int; 2147483647 is not.
• Printing dp[k] without checking whether its value is still BESAR.

Problem 3 — Number of ways

Problem. Count the ways to make k, where order does not matter.

How to think about it. This is the only DP problem in this chapter whose answer depends on the order of the two loops:

• coins outside, values inside → counts combinations (1+3 is the same as 3+1),
• values outside, coins inside → counts orderings (1+3 differs from 3+1).

This problem asks for the first. Imagine each coin being offered once to all the values: since coin 3 is only offered after coin 1 is finished, an arrangement that uses coin 1 after coin 3 is never formed.

The base case is dp[0] = 1: there is exactly one way to make the value zero, namely taking nothing.

Walkthrough.

dp[0] = 1;
for (int i = 0; i < m; i++)
    for (int v = c[i]; v <= k; v++)
        dp[v] = (dp[v] + dp[v - c[i]]) % MOD;

cout << dp[k] << "\n";

For coins 1 3 4 and k = 6 the answer is 4: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+1+4.

Tests.

The first case checks that order is not treated as different: 3 + 3 and 1 + 1 + 4 are each counted once. If your answer is much larger, the loop order is most likely reversed — coins inside, values outside — which counts 1 + 3 and 3 + 1 as two different ways.

Common mistakes.

• Swapping the loop order, then getting 9 instead of 4.
• Writing dp[0] = 0, so the entire answer becomes zero.

Problem 4 — 0/1 knapsack

Problem. The largest value with weight limit W.

How to think about it. A two-dimensional state: dp[i][b] = the largest value using the first i items with weight limit b. For each item there are only two choices — take it or not — and DP tries both.

The phrase "each item at most once" is what makes row i allowed to look only at row i − 1. If it looked at its own row, the same item could be taken many times (and that is exactly the formula for the coin problem where repetition is allowed).

Walkthrough.

for (int i = 1; i <= n; i++) {
    for (int b = 0; b <= W; b++) {
        dp[i][b] = dp[i - 1][b];
        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];
    }
}
cout << dp[n][W] << "\n";

On the homework file's example, greedy by value per weight answers 10 while DP answers 14 — one "efficient" item of weight 6 loses to two items of weight 5.

Tests.

The second case is the same as the tracing table in Chapter 13, so you can compare your dp contents cell by cell if the answer is off. The first case tests the "not taken" branch: the answer is 0, not the item's value.

Common mistakes.

• Storing data starting from index 0 but writing the transition with dp[i-1], so the first item is skipped. Pick one numbering style and be consistent.
• Declaring the array dp[105][10005] as a local variable inside main. Its size is about 4 MB — too large for stack memory. Put it in a global variable.

Challenge — Longest increasing subsequence

Problem. The length of the longest increasing subsequence, n ≤ 5,000.

How to think about it. The right state is dp[i] = the length of the longest increasing subsequence that ends exactly at element i. The words "ends exactly at" matter: without them, the transition cannot be written, because we need to know the value of the last element to decide whether the next element may be appended.

The transition: look at every j < i; if a[j] < a[i], the subsequence ending at j may be extended to i.

The answer is not dp[n-1], but the largest value in the whole dp — because the longest subsequence does not necessarily end at the last element.

The number of steps is O(n²) = 25 million for n = 5,000. That fits. (There is an O(n log n) method used in problems with larger constraints, but it is outside the scope of this book.)

Walkthrough.

int terpanjang = 0;
for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++)
        if (a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
    if (dp[i] > terpanjang) terpanjang = dp[i];
}
cout << terpanjang << "\n";

For 3 1 4 1 5 9 2 6 the answer is 4.

Tests.

The third row is the edge case that is most often wrong: equal values must not be treated as increasing. If the condition is written a[j] <= a[i], the answer becomes 6 and every subtask with repeated data is wrong too.

Common mistakes.

• Printing dp[n-1]. For 1 2 3 0 the answer is 3, but dp[3] = 1.
• Using a[j] <= a[i], which allows equal values and turns the problem into "non-decreasing".
• Forgetting dp[i] = 1 as the initial value, so elements that cannot be appended to anything end up with value zero.

OSN-style exercises — walkthrough

The answer files are in exercises/13/osn/solutions/.

Problem 1 — Grid Paths with Obstacles

The state. dp[i][j] is the number of paths from the top-left cell to cell (i, j).

How to think about it. A cell can only be entered from above or from the left, and those two ways never produce the same path. So dp[i][j] = dp[i-1][j] + dp[i][j-1]. A blocked cell has value 0, because no path may end there. The starting cell has value 1 — that is the "empty path" that has not moved anywhere yet.

Note the order of the checks in the code: the obstacle is checked first, then the starting cell. If the starting cell itself is blocked, the answer is 0, and this order handles it without an extra branch.

Since each cell is computed from the cells above it and to its left, the loop must run from the top row down and from the left column to the right.

Size of the answer. On a 17 × 17 map without obstacles, the number of paths is 601,080,390. It still fits in int, but barely; long long removes the doubt.

Walkthrough.

vector<vector<long long>> dp(r, vector<long long>(c, 0));

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        if (peta[i][j] == '#') { dp[i][j] = 0; continue; }
        if (i == 0 && j == 0)  { dp[i][j] = 1; continue; }

        long long total = 0;
        if (i > 0) total += dp[i - 1][j];
        if (j > 0) total += dp[i][j - 1];
        dp[i][j] = total;
    }
}

cout << dp[r - 1][c - 1] << "\n";

Tests.

Common mistakes.

• Setting dp[0][j] = 1 for the entire first row without checking for obstacles. One obstacle in the first row should cut off the rest of that row.
• Reading the map with getline after cin >> r >> c without clearing the rest of the line, so the first map row is read as empty. Using cin >> peta[i] avoids this problem entirely.
• Running the loop from right to left, so dp[i][j-1] is read before it is filled.

Problem 2 — No Neighbors

The state. dp[i] is the largest profit that can be obtained from the first i stalls.

How to think about it. For stall i there are only two possibilities, and together they cover every case:

• that stall is not rented, so the result equals dp[i-1];
• that stall is rented, so its neighbor may not be, and the result is dp[i-2] + A[i].

Take the larger one. The initial states are dp[0] = 0 (no stalls) and dp[1] = A[1].

Saving memory. The formula only touches the last two values, so the whole array does not need to be stored — two shifting variables are enough. For N = 200,000 a long long array takes 1.6 MB, which is actually still safe; but this habit becomes important when the table is two-dimensional.

Walkthrough.

long long duaLalu = 0, satuLalu = 0;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;

    long long sekarang = satuLalu;
    if (duaLalu + x > sekarang) sekarang = duaLalu + x;

    duaLalu = satuLalu;
    satuLalu = sekarang;
}

cout << satuLalu << "\n";

The order of the last three lines matters: duaLalu ("two back") must receive the old value of satuLalu ("one back"), not the new one.

Tests.

Common mistakes.

• Greedily taking alternating stalls — all odd or all even positions. For 3 2 7 10 12 5 that gives 22 and 17, so it happens to be correct; for 2 1 1 2 it gives 3, while the answer is 4.
• Using int for the total: at most 10⁵ non-adjacent stalls can be rented, so the total can reach 10⁵ × 10⁹ = 10¹⁴.
• Forgetting that the answer may come from renting nothing, so the initial value is filled with a negative number.

Problem 3 — Split into Two Equal Weights

The state. bisa[s] ("possible") is true if a total weight of exactly s can be formed from the sacks processed so far.

How to think about it. Two trucks with equal weight means each carries half of the total. If the total is odd, the answer is immediately TIDAK — a one-line check that saves the entire computation.

If it is even, the question becomes: is there a set of sacks that sums to exactly total / 2? This is the subset sum problem, and its solution is a boolean table of length total / 2 + 1. Initially only the sum 0 can be formed. Each new sack adds possibilities: if s − w can already be formed, then s can too.

Why the sum loop runs backward. If s runs upward, the value bisa[s - w] being read might have just been filled by the same sack in this round, so one sack gets used twice. Running backward guarantees that bisa[s - w] still holds the state from before this sack was processed. This is the difference between "each item once" and "items may repeat" mentioned in the Tips section.

Table size. The largest total is 100 × 100 = 10,000, so the table has length at most 5,001 and the whole computation is 100 × 5,000 = 5 × 10⁵ steps.

Walkthrough.

if (total % 2 != 0) { cout << "TIDAK\n"; return 0; }

int separuh = total / 2;
vector<bool> bisa(separuh + 1, false);
bisa[0] = true;

for (int i = 0; i < n; i++) {
    for (int s = separuh; s >= w[i]; s--) {
        if (bisa[s - w[i]]) bisa[s] = true;
    }
}

cout << (bisa[separuh] ? "YA\n" : "TIDAK\n");

Tests.

The second case matters: the total is 8, so the odd/even check does not help. The answer must come from the table.

Common mistakes.

• Running the sum loop from small to large, so one sack can be used many times and 1 2 5 is answered YA.
• Forgetting bisa[0] = true, so the whole table stays wrong.
• Assuming an even total is enough to answer.

If you are still stuck

• You do not know what the state is → Chapter 13, step 1 of the five steps. Write dp[i] as a complete sentence before writing code.
• The answer is slightly off → check the base case; dp[0] = 0 and dp[0] = 1 are two different problems.
• Not sure whether the problem is DP or not → Chapter 13, section Recognizing DP problems.

Once a state can be written as a sentence, the rest usually follows. If it cannot be yet, writing code will only prolong the confusion.