Dynamic programming · HTML
dp[i] denotes an optimum/count for the first i items or a solution ending at i. A transition dp[i]=Aggregate(dp[j],local(j,i)) ranges over a finite neighborhood or all j<i, with explicit empty-prefix or first-item bases.
Recognition signals
- The input is a one-dimensional sequence or timeline.
- The answer advances by prefix and the suffix needs only a prefix summary.
- Many decision histories revisit the same prefix state.
- The current decision depends on the previous item or a small set of earlier positions.
- The output is an optimum, feasibility, or count rather than explicit enumeration.
False friends
| Signal | Why it is different |
|---|
| A provably exchangeable local choice | If one choice never causes regret, greedy is simpler; DP is for historical branches that must coexist. |
| Future behavior depends on a chosen set | An index alone is insufficient when the selected subset matters; use a bitmask or richer state. |
| A fixed-window statistic | Without decision overlap, a sliding window or prefix aggregate is the more direct model. |
Core invariant
After processing i, every state through i equals the true value under its definition, and every future transition reads only these finalized states.
State, transition, and processing order
| Item | Definition |
|---|
| State | A prefix/position plus the minimal summary the future needs; optionally a parent link for reconstruction. |
| Transition | Enumerate every possible previous state of the last step, combine its answer with the local contribution, then aggregate by min, max, sum, or logical OR. |
| Frontier / order | The next index in dependency topological order, normally left to right; fixed-width dependencies permit rolling storage. |
Python skeleton
def min_linear_cost(cost):
n = len(cost)
if n == 0: return 0
if n == 1: return cost[0]
prev2, prev1 = cost[0], cost[1]
for i in range(2, n):
cur = cost[i] + min(prev1, prev2)
prev2, prev1 = prev1, cur
return min(prev1, prev2)
Correctness sketch
- Base states directly cover the smallest domains.
- Assume prior states meet their definitions; every complete solution reaching i has one last predecessor included by the transition.
- Aggregating this complete set of correct candidates yields the correct state i, and induction reaches the answer.
Complexity
| Time | Space | Parameters |
|---|
| O(n·d), where d is predecessors checked per state; O(n) for fixed d | O(n), compressible to O(d) for fixed dependence | n is sequence length and d transition indegree. |
Edge cases
- empty sequence
- length one or two
- negative values changing base semantics
- count overflow or modulus
- whether the answer is dp[n] or an aggregate of tail states
Error patterns
| Pattern | Why it fails / fix |
|---|
| Writing a recurrence before defining state | ‘First i items’ and ‘ending at i’ produce different indices, bases, and answers. |
| Overwriting a needed predecessor | Draw dependencies before rolling compression and preserve every old value required by the update. |
| A base case fitted to examples | Initialization must follow the state definition, not convenient sample values. |
| Returning only the last cell | Some processes may end in several tail states that require a final aggregate. |
Selection and exclusion rules
- Define dp[i] in one exact sentence.
- Derive transitions by asking what the last step could be.
- Choose iteration order only after identifying the dependency DAG.
- Compress after correctness, and keep parents when a witness is required.
Original micro-example
| Part | Detail |
|---|
| Result | The minimum is min(1,7)=1, illustrating that the answer need not be the last state. |
| Setup | Segment costs are [4,1,6]; start on either of the first two segments, move one or two segments, and finish by stepping beyond the end. |
| Trace | Cost to land on segment three is 6+min(4,1)=7; exit may follow segment two or three. |
Recall prompts
My notes