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.

Largest sum of any contiguous run. dp[i] is the best run ending exactly at i: either extend the run ending at i - 1, or restart at i if that run only drags the sum down. The overall answer is the largest dp[i]. Filled in place over the values.

Check your understanding

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

Run ending before is -2, value here is 1. Extend or restart?
- Extend the run
- Restart here
Answer: Restart here. The run so far is negative: it can only lower the sum, so drop it and start fresh.
Run ending before is 1, value here is -3. Extend or restart?
- Extend the run
- Restart here
Answer: Extend the run. The run so far is not negative, so carrying it adds 1 for free.
Run ending before is -2, value here is 4. Extend or restart?
- Extend the run
- Restart here
Answer: Restart here. The run so far is negative: it can only lower the sum, so drop it and start fresh.
Run ending before is 4, value here is -1. Extend or restart?
- Extend the run
- Restart here
Answer: Extend the run. The run so far is not negative, so carrying it adds 4 for free.
Run ending before is 3, value here is 2. Extend or restart?
- Extend the run
- Restart here
Answer: Extend the run. The run so far is not negative, so carrying it adds 3 for free.
Run ending before is 5, value here is 1. Extend or restart?
- Extend the run
- Restart here
Answer: Extend the run. The run so far is not negative, so carrying it adds 5 for free.
Run ending before is 6, value here is -5. Extend or restart?
- Extend the run
- Restart here
Answer: Extend the run. The run so far is not negative, so carrying it adds 6 for free.
Run ending before is 1, value here is 4. Extend or restart?
- Extend the run
- Restart here
Answer: Extend the run. The run so far is not negative, so carrying it adds 1 for free.

How it runs, step by step

Largest sum of any contiguous run. dp[i] is the best run ending exactly at i: either extend the run ending at i - 1, or restart at i if that run only drags the sum down. The overall answer is the largest dp[i]. Filled in place over the values.
Finding the maximum subarray sum with one running best per position.
Value 1. Extending the run gives -1, restarting gives 1. The old run only hurts, so restart: dp[1] = 1. New best, 1.
Position 1: the best run ending here is 1. The best overall is 1.
Value -3. Extending the run gives -2, restarting gives -3. Extend: dp[2] = -2. Best stays 1.
Position 2: the best run ending here is -2. The best overall is 1.
Value 4. Extending the run gives 2, restarting gives 4. The old run only hurts, so restart: dp[3] = 4. New best, 4.
Position 3: the best run ending here is 4. The best overall is 4.
Value -1. Extending the run gives 3, restarting gives -1. Extend: dp[4] = 3. Best stays 4.
Position 4: the best run ending here is 3. The best overall is 4.
Value 2. Extending the run gives 5, restarting gives 2. Extend: dp[5] = 5. New best, 5.
Position 5: the best run ending here is 5. The best overall is 5.
Value 1. Extending the run gives 6, restarting gives 1. Extend: dp[6] = 6. New best, 6.
Position 6: the best run ending here is 6. The best overall is 6.
Value -5. Extending the run gives 1, restarting gives -5. Extend: dp[7] = 1. Best stays 6.
Position 7: the best run ending here is 1. The best overall is 6.
Value 4. Extending the run gives 5, restarting gives 4. Extend: dp[8] = 5. Best stays 6.
Position 8: the best run ending here is 5. The best overall is 6.
Maximum subarray sum 6, from index 3 to 6. One pass, one comparison per element: O(n). The cell values are the best run ending at each index.
The maximum subarray sum is 6, from index 3 to 6.

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.

1// The best for an amount is one more than the best for that amount minus a coin, over every coin that fits.2function minCoins(coins, amount) {3  4  return -1;5}6

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

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.

Dynamic programmingWikipedia
Introduction to dynamic programmingcp-algorithms
Maximum subarray problemWikipedia
Longest increasing subsequencecp-algorithms
Knapsack problemcp-algorithms