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. At each house 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 house i
            dp[i-2] + nums[i])  # take house i
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.

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.

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.