1D DP Patterns

Dynamic Programming, lesson 2 of 3

1D DP Patterns

Three shapes that cover most 1D problems: take or skip, unbounded choices, and best-ending-here (LIS).

14 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

In 1D DP the state is a single index or amount: dp[i] = the answer for the first i items (or for amount i). Three transition shapes come up again and again:

Shape Question at each i Classic
Take / skip use item i or not? House Robber
Unbounded choices which option was used last? Coin Change
Best ending here which earlier j do I extend? LIS

Take / skip: House Robber. Houses in a row hold money; you can't rob two neighbours. Let dp[i] be the most money from the first i houses. For the last of them, nums[i-1], you either skip it (keep the best so far) or take it (its money plus the best from two houses back):

dp[i] = max(dp[i-1],              # skip it
            dp[i-2] + nums[i-1])  # take it
Example

House Robber, traced

dp has one extra slot so dp[0] = 0 means "no houses yet": that padding removes most edge cases. Only dp[i-1] and dp[i-2] are ever read, so two variables are enough.

Quiz

What does this O(1)-space version print?

Unbounded choices: Coin Change. Fewest coins to make amount, using each coin as many times as you like. State: dp[a] = fewest coins that sum to a. The last coin used was some c, leaving a - c:

dp[a] = min(dp[a - c] + 1 for c in coins if c <= a)
dp[0] = 0, everything else starts at infinity

"Infinity" means "impossible so far": if it's still there at the end, the answer is -1.

Walkthrough

Fewest coins: coins [1, 3, 4], amount 6

0∞∞∞∞∞∞0123456
Step 1 of 7

dp[0] = 0: no coins make 0. Every other amount starts at ∞, "impossible so far".

dp[a] being filled
dp[a - c] for each coin c ≤ a
answer
Example

Greedy vs DP

Greedy grabs 4 and needs 4+1+1. DP tries every last coin and finds 3+3. When "always take the biggest" can be fooled, reach for DP.

Counting variant. To count the combinations that make an amount (Coin Change II), the transition adds instead of taking a min, and the base case is dp[0] = 1 (one way to make 0: no coins). The loop order decides what you count:

  • coins in the outer loop: each coin is considered once, in a fixed order, so {1, 2} and {2, 1} are the same combination
  • amounts in the outer loop: every order is counted separately (permutations)
Quiz

What does this print?

Best ending here: Longest Increasing Subsequence. Sometimes "the first i items" isn't enough information, because the next choice depends on which item you ended with. Then define the state as "the best answer that ends exactly at i":

dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i])
(or 1 if there is no such j)
answer = max(dp)   # the best can end anywhere

That's O(n²): for each i, scan every earlier j.

Walkthrough

LIS ending at each index

nums10925371011801234567dp1111111101234567
Step 1 of 7

Every number alone is an increasing subsequence, so dp starts all 1. 10, 9 and 2 have no smaller number before them: they stay 1.

index i
smaller earlier numbers / the best dp among them
answer
Example

LIS in O(n²)

dp[6] = 4 comes from 2 → 5 (or 3) → 7 → 101. The answer is max(dp), not dp[-1]: the last number doesn't have to be in the best subsequence.

Quiz

In Coin Change (fewest coins), how should the table start?

Exercise

Count coin combinations

Write count_combos(coins, amount) that returns how many combinations of coins (unlimited supply of each) add up to amount. Order doesn't matter: 1+2 and 2+1 are the same combination.

count_combos([1, 2, 5], 5) is 4: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.