Dynamic programming · HTML
dp[i][s] is the best value after time i in mode s. Update dp[i][s']=Agg_s(dp[i-1][s]+cost(s→s',i)) over edges allowed by the state graph.
Recognition signals
- At each time, the process occupies one of a few mutually exclusive modes.
- Actions change eligibility such as holding, idle, cooldown, or phase.
- The future needs the current mode but not the full history.
- A small counter or stage can encode restrictions.
- The verbal rules can be drawn as a compact state graph.
False friends
| Signal | Why it is different |
|---|
| Exponentially many modes | This is not a finite-state model; consider a bitmask or another structured state. |
| Independent per-step rewards | If history imposes no constraint, aggregate locally without DP. |
| A provably regret-free action | When one greedy rule is valid, state-machine DP is unnecessary machinery. |
Core invariant
After time i, each state value is the optimum among every legal history ending in that mode, and no illegal history enters a finite state.
State, transition, and processing order
| Item | Definition |
|---|
| State | Time i and finite mode s, with unreachable modes initialized to positive or negative infinity as appropriate. |
| Transition | For every legal state-graph edge, extend the prior source state with the current action contribution into the target state. |
| Frontier / order | Time advances forward; each round derives new from old so multiple edges cannot be traversed accidentally at one instant. |
Python skeleton
def max_gain(prices):
# States: flat or holding one unit; any number of transactions.
flat, hold = 0, float('-inf')
for price in prices:
old_flat, old_hold = flat, hold
flat = max(old_flat, old_hold + price)
hold = max(old_hold, old_flat - price)
return flat
Correctness sketch
- Initially flat=0 and hold is unreachable, exactly describing zero processed times.
- Every history ending in a target state has a final action corresponding to one incoming state edge, all of which are enumerated.
- Source states are optimal by induction, so aggregation makes each target optimal; choose among allowed terminal states.
Complexity
| Time | Space | Parameters |
|---|
| O(n·|E_s|), which is O(n) for a fixed graph | O(|S|) | n is time count and S/E_s are modes/legal transitions. |
Edge cases
- empty timeline
- initially reachable modes
- required terminal mode
- whether same-time chained actions are legal
- transaction or phase dimensions
- arithmetic involving infinity sentinels
Error patterns
| Pattern | Why it fails / fix |
|---|
| In-place updates using current-round values | If chained actions are forbidden, derive every new state from an old snapshot. |
| States overlap or omit needed history | Overlap double-counts histories; insufficiency merges histories with different futures. |
| Initializing illegal modes to zero | That creates value from nowhere; an unreachable maximizing state needs negative infinity. |
| Drawing nodes without action labels | Edge conditions and gains define the recurrence; names alone do not. |
Selection and exclusion rules
- List mutually exclusive modes sufficient for the future.
- Draw every legal edge with its action value.
- Separate old and new time layers.
- Specify allowed initial and terminal modes.
Original micro-example
| Part | Detail |
|---|
| Result | The terminal flat value is 3, corresponding to buy at 1 and sell at 4. |
| Setup | Prices are [3,1,4], with at most one item held. |
| Trace | At price 1, hold=max(-3,-1)=-1; at price 4, flat=max(0,-1+4)=3. |
Recall prompts
My notes