1-D DP: Coins & LIS

Making change, scheduling, stock prices, text layout: many problems shrink to one array where each cell is “the best answer for a prefix or an amount”. Learn the two classic shapes here and you will recognise dozens of others.

intermediate⏱ 14 min read

←Builds on

10DP Fundamentals: Memo & Table1-D DP is the table form of a memo with one index, filled left to right.7The Greedy Idea & When It FailsCoin change is where greedy failed; DP gets it right by trying every coin.5Balanced Trees & set / mapO(n log n) LIS keeps the best tails sorted and finds each spot with lower_bound, as in std::set.

Leads to→

10DP on GridsGrid DP is 1-D DP with a second index: each cell reads the one above and the one to the left.11Prefix Function & KMPThe prefix function is filled left to right, each value built from earlier ones.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Where greedy breaks: coins {1, 3, 4}

Pay 6 with as few coins as possible, using coins of value 1, 3 and 4. Greedy grabs the biggest coin that fits: 4, then 1, then 1, three coins. But 3 + 3 uses only two.

Greedy failed because its first choice looked good locally and ruined the rest. DP never commits early: for every amount it remembers the best answer, and it builds bigger amounts from those.

The state is one sentence: dp[a] = the fewest coins that make exactly amount a. The base is dp[0] = 0. For any other a, the last coin you used was some c, and before it you had made a − c optimally. So

dp[a] = 1 + min over coins c ≤ a of dp[a − c]

with dp[a] = ∞ when no coin fits. Fill a = 1, 2, …, A and the answer is dp[A].

02Filling the array, and getting the coins back

For coins {1, 3, 4} the array for amounts 0..6 is 0 1 2 1 1 2 2. Look at dp[6]: it compares dp[5] (then coin 1), dp[3] (coin 3) and dp[2] (coin 4). The smallest is dp[3] = 1, so dp[6] = 2.

The table tells you *how many* coins; to know *which*, store the winning coin choice[a] while filling. Then walk back: from 6 take choice[6] = 3, from 3 take choice[3] = 3, reach 0. Storing the winning choice and walking back is the standard reconstruction trick for every DP in this stage.

Cost: A amounts × k coins = O(A·k) time, O(A) memory. Two common variations use the same array:

number of ways to pay A: replace min with + and set dp[0] = 1. With the amount loop outside, as here, this counts ordered sequences (1+3 and 3+1 are two ways); to count combinations, put the coin loop outside and the amount loop inside;
can we pay at all: store true/false.

Three candidate arrows into dp[6]; the green one wins.

03Longest increasing subsequence in O(n²)

Given 3 1 4 1 5 9 2 6, find the longest subsequence (keep order, skip freely) that strictly increases. Here it is 3 4 5 9, length 4.

The trick is choosing the right state. dp over “the first i elements” is awkward, because to extend a sequence you need to know its last value. So define

len[i] = length of the longest increasing subsequence that ends exactly at index i.

Then len[i] = 1 + max(len[j]) over earlier j with a[j] < a[i], or 1 if there is none. The answer is the largest len[i], not len[n−1], since the best sequence can end anywhere. Keep prev[i] = the j that won, and walk back from the best i to print the sequence.

Two nested loops: O(n²). Fine for n of a few thousand.

04The binary search speedup: O(n log n)

For n = 10⁵, O(n²) is too slow. Keep a different array instead:

tails[k] = the smallest possible last value of an increasing subsequence of length k + 1 seen so far.

A small tail is good: it is easier to extend later. tails is always sorted, so for each new value x:

find the first tail ≥ x with binary search (lower_bound);
if there is none, append x (a longer sequence now exists);
otherwise replace that tail with x (same length, smaller ending).

On 3 1 4 1 5 9 2 6, tails ends as 1 2 5 6. Its length, 4, is the LIS length. Careful: 1 2 5 6 itself is not necessarily a real subsequence, only its length is guaranteed. Each step is one binary search, so the total is O(n log n). For non-decreasing sequences, use upper_bound instead.

Green: appended (the LIS grew). Orange: replaced with a smaller tail.

Cost at a glance

Coin change, A = amount, k = coinsO(A·k)

LIS, classic DPO(n²)

LIS with tails + binary searchO(n log n)

Remember

A 1-D DP needs one sentence of state, like “dp[a] = fewest coins for exactly a” or “len[i] = longest run ending at i”.
Store the winning choice while filling; walking those choices backwards rebuilds the actual answer.
LIS drops from O(n²) to O(n log n) by keeping the smallest tail for each length and finding the spot by binary search.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: First watch dp[a] fill and the coins come back out; then in the LIS part compare the len[] numbers on the bars with the much shorter tails[] row underneath.

Interactive visualizerfocus here, then space ← →

Coin change {1,3,4}, amount 6 (dp[a] = min coins)

a	0	1	2	3	4	5	6
dp	0	∞	∞	∞	∞	∞	∞

reconstructed coins

∅

Coins {1,3,4}, amount 6. DP considers every coin for every smaller amount. dp[0] = 0.

Pseudocode

 1 coin change: dp[0]=0, dp[a]=∞ 2   for each coin c ≤ a: dp[a] = min(dp[a], dp[a-c] + 1) 3   reconstruct via stored choice[] 4 LIS: len[i] = 1 + max(len[j]) over j<i with a[j]<a[i] 5   answer = max len[i]   (tails[] + binary search: O(n log n))

1 / 1

Check

Three questions. Pick an answer to see why.

Coins {1, 5, 6, 9}, amount 11. What is dp[11]?

Why is the LIS answer max(len[i]) and not len[n−1]?

tails is [2, 5, 7] and the next value is 6. What happens?

Practice

Real problems to lock it in, easiest first.

LeetCodeCoin Change intermediate↗CSESMinimizing Coins intermediate↗CSESCoin Combinations I intermediate↗LeetCodeLongest Increasing Subsequence intermediate↗CSESIncreasing Subsequence advanced↗