AlgoScope

DP in One Row

algorithmintermediateTime O(n) to O(n^2)Space O(n)

When the state is a single index, the DP table is just an array, and each cell is built from a few cells before it. Fibonacci and stairs read two back. Coin change reads one back per coin and keeps the best. House robber and maximum subarray decide between two options at every index. LIS reads every earlier smaller value. Same recipe each time: base cases, a rule, left to right.

00112345678910

Fibonacci by tabulation: f(0) = 0 and f(1) = 1 are known, and every later value is the sum of the two before it. Fill left to right and each value is computed exactly once, where the naive recursion would recompute it exponentially often.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 9, with their answers.

  1. dp[1] = 1 and dp[0] = 0. What is dp[2]?

    • 1
    • 0
    • 2

    Answer: 1. The two cells before it add up: 1 + 0 = 1.

  2. dp[2] = 1 and dp[1] = 1. What is dp[3]?

    • 2
    • 1

    Answer: 2. The two cells before it add up: 1 + 1 = 2.

  3. dp[3] = 2 and dp[2] = 1. What is dp[4]?

    • 3
    • 2

    Answer: 3. The two cells before it add up: 2 + 1 = 3.

  4. dp[4] = 3 and dp[3] = 2. What is dp[5]?

    • 5
    • 6
    • 4

    Answer: 5. The two cells before it add up: 3 + 2 = 5.

  5. dp[5] = 5 and dp[4] = 3. What is dp[6]?

    • 8
    • 15
    • 6

    Answer: 8. The two cells before it add up: 5 + 3 = 8.

  6. dp[6] = 8 and dp[5] = 5. What is dp[7]?

    • 13
    • 40
    • 9

    Answer: 13. The two cells before it add up: 8 + 5 = 13.

  7. dp[7] = 13 and dp[6] = 8. What is dp[8]?

    • 21
    • 104
    • 14

    Answer: 21. The two cells before it add up: 13 + 8 = 21.

  8. dp[8] = 21 and dp[7] = 13. What is dp[9]?

    • 34
    • 273
    • 22

    Answer: 34. The two cells before it add up: 21 + 13 = 34.

  9. dp[9] = 34 and dp[8] = 21. What is dp[10]?

    • 55
    • 714
    • 35

    Answer: 55. The two cells before it add up: 34 + 21 = 55.

How it runs, step by step

  1. Fibonacci by tabulation: f(0) = 0 and f(1) = 1 are known, and every later value is the sum of the two before it. Fill left to right and each value is computed exactly once, where the naive recursion would recompute it exponentially often.

    Filling a table of fibonacci values from 0 to 10, each the sum of the two before it.

  2. dp[2] = dp[1] + dp[0] = 1 + 0 = 1.

    Index 2 is 1 plus 0, which is 1.

  3. dp[3] = dp[2] + dp[1] = 1 + 1 = 2.

    Index 3 is 1 plus 1, which is 2.

  4. dp[4] = dp[3] + dp[2] = 2 + 1 = 3.

    Index 4 is 2 plus 1, which is 3.

  5. dp[5] = dp[4] + dp[3] = 3 + 2 = 5.

    Index 5 is 3 plus 2, which is 5.

  6. dp[6] = dp[5] + dp[4] = 5 + 3 = 8.

    Index 6 is 5 plus 3, which is 8.

  7. dp[7] = dp[6] + dp[5] = 8 + 5 = 13.

    Index 7 is 8 plus 5, which is 13.

  8. dp[8] = dp[7] + dp[6] = 13 + 8 = 21.

    Index 8 is 13 plus 8, which is 21.

  9. dp[9] = dp[8] + dp[7] = 21 + 13 = 34.

    Index 9 is 21 plus 13, which is 34.

  10. dp[10] = dp[9] + dp[8] = 34 + 21 = 55.

    Index 10 is 34 plus 21, which is 55.

  11. f(10) = 55. 10 cells, each computed once from two known cells: O(n) time. Only the last two are ever needed, so O(1) space is possible too.

    The answer is 55.

Write it yourself

Define minCoins(coins, amount) and return the fewest coins that make the amount, or -1 when none do. It runs in your browser against this lesson's own 2 examples.

// The best for an amount is one more than the best for that amount minus a coin, over every coin that fits.function minCoins(coins, amount) {    return -1;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

  • A 1D DP is an array filled left to right; the rule says which earlier cells each one reads.
  • Take-or-skip (house robber) and extend-or-restart (Kadane) are two-option rules, so a comparison per cell.
  • If the rule only reads a fixed number of cells back, the table can shrink to those few variables.

Topics covered

Related

Where this is used

TypesettingParagraph line breaking in TeX

TeX does not break greedily at the last word that fits on each line. Knuth and Plass treat every legal break point, each interword space and each hyphenation point, as a cell: dp[i] is the lowest total demerits for setting the paragraph up to break point i, read from the earlier break points that could start its final line. Demerits are built from the badness of a line, TeX's measure of how far its spaces had to stretch or shrink. One left to right pass therefore optimises the paragraph as a whole, which is why TeX rarely leaves the loose or tight lines a greedy wrapper produces.

CompressionOptimal parsing in Zopfli and LZMA

At every byte a compressor can emit a literal or any one of several matches of different lengths, and the longest match now can cost more bits later. gzip decides locally, looking at most one position ahead before it commits; Zopfli and LZMA fill dp[i] = the fewest bits to encode the first i bytes, each cell reading back one cell per candidate match. That is why Zopfli emits deflate streams a few percent smaller than gzip's best, which ordinary gunzip still reads, and why it takes around eighty times longer to do it.

Developer toolsPatience diff in git

git diff --patience first pairs up lines that occur exactly once in both files, then keeps the longest increasing subsequence of those pairs so the surviving anchors appear in the same order on both sides. Everything between consecutive anchors is recursed into or reported as an edit. LIS is the exact fit because the only constraint on an anchor is that it sit after every anchor chosen before it, in both files at once.

NetworkingViterbi decoding of convolutional codes

Wi-Fi, GSM and deep space links protect bits with a convolutional code, and the decoder runs one DP column per received symbol. The column holds a score per encoder state instead of a single number, but it is built only from the column before it, so the scores need two columns rather than the whole transmission, the same shrink that turns the stairs table into two variables. The survivor pointer stored per cell is the part that cannot shrink, because walking it back is how the bits are recovered.

Why it works this way

Why house robber saves the old value before overwriting

take and skip are the last cells of two rolled up tables, best with the previous house robbed and best without it, so both have to be computed from the previous step's values. Writing skip = max(skip, take) first and then take = skip + x reads the new skip and quietly allows robbing two adjacent houses. The other cost of rolling the tables up is that you can no longer say which houses were taken; keep the array, or a choice flag per cell, when you need the answer and not just its value.

Coin change reuses each coin, and the loop order is why

dp[a - c] was finished on an earlier amount that had already seen every coin, so the same coin can be picked again and again, which is what min coins wants. Put the coin on the outside and count the amount downward instead, and dp[a - c] still holds the value from before this coin existed, giving each coin at most once. That single change is the whole difference between unbounded and 0/1 knapsack.

Adding one to the unreachable marker

dp[a - c] + 1 when dp[a - c] is Int.MAX_VALUE wraps around to Int.MIN_VALUE, so an amount that cannot be made looks cheaper than every real answer and poisons every cell above it. The code guards with an explicit check before the addition. The other standard fix is to fill the table with amount + 1, a value no real answer can reach, so the arithmetic never overflows and the final test is dp[amount] > amount.

Maximum subarray of an all negative array

max(a[i], endingHere + a[i]) restarts whenever the running sum has gone negative, because a negative prefix can only make whatever follows worse. Start best at 0 rather than a[0] and [-5, -2, -9] returns 0, the empty subarray, which is almost never what was asked. Seeding both variables from a[0] and looping from index 1, as here, keeps at least one element in the answer.

Read more

Next up