Linear DP: one entry per position
The answer at each position comes from a fixed number of nearby positions. One pass along the sequence, often with O(1) memory.
The pattern
Many sequence problems have this shape: the answer for position i depends on the answers for a few positions just before it (or just after it), and nothing else. Climbing stairs one or two steps at a time, robbing houses without taking two neighbours, decoding a string of digits one or two at a time, jumping along an array.
Linear DP template
dp[i]
- = opt over a small fixed set of steps k (for example k ∈ {1, 2}) of
- contribution(i, k) ⊕ dp[i − k].
order
- left to right (or right to left if dp[i] reads later positions).
answer
- usually dp at the last (or first) position.
Because each entry reads only the last few, the table can shrink to a handful of variables.
Worked example: the cheapest way up
Step i costs cost[i]; from a step you climb one or two steps; you start below step 0 or step 1 and
must get past the top. The cheapest way to stand on step i is cost[i] + min(dp[i − 1], dp[i − 2]).
Costs 10, 15, 20, 5, 25, 10.
-
Step 1 / 5cost10015120253254105dp100151·2·3·4·5
Base cases: dp[0] = 10, dp[1] = 15.
-
Step 2 / 5cost10015120253254105dp100151302·3·4·5
Step 2: 20 + min(15, 10) = 30.
-
Step 3 / 5cost10015120253254105dp100151302203·4·5
Step 3: 5 + min(30, 15) = 20.
-
Step 4 / 5cost10015120253254105dp100151302203454·5
Step 4: 25 + min(20, 30) = 45.
-
Step 5 / 5cost10015120253254105dp100151302203454305
Step 5: 10 + min(45, 20) = 30. Past the top from step 4 or 5: min(45, 30) = 30.
How to recognise it
- A single sequence, scanned once.
- A decision at each position with a constant number of options (take or skip, one step or two).
- The future depends on the past only through the last few positions.
k is the number of positions each entry reads.
The problems in this module: