Dynamic Programming State Design
Define a dynamic-programming state as the answer to a precise subproblem. Then derive its transitions, base cases and dependency order. Complexity follows from the number of states and the work per state, not merely from the presence of a table.
Decide whether the caller needs only the optimum value or the actual selected solution before compressing storage. Removing earlier rows can preserve a value while discarding the history needed for reconstruction. The most important optimization is often getting the state meaning right first.
TL;DR
- Define each DP state as the answer to a precise subproblem before writing any table.
- Derive transitions, base cases, and a valid dependency order from that definition.
- Complexity is number of states × work per state, not the mere presence of a table.
- Decide whether callers need only the optimal value or the chosen solution before compressing storage — rolling arrays can discard what reconstruction needs.
- Mark impossible states explicitly so infeasible targets are never reported as achievable.
Quick Example
This Python example solves the optimum value of a small 0/1 knapsack under positive integer weights and nonnegative integer capacity. Each item can be used at most once. Additional tests compared the result against exhaustive subset enumeration across several capacities.
Descending capacity order keeps the current item from being reused within the same item iteration. The one-item case catches a common ascending-loop error: weight two and value three must not produce value six at capacity four. The function returns a value only and does not reconstruct item identities or validate every possible malformed input.
Core Concepts
Say what a state means in words
For the full-table version, define F(i,c) as the best value achievable using the first i items with total weight at most c. The item prefix and remaining capacity describe the choices still relevant to that subproblem. The definition also establishes that unused capacity is allowed.
MIT's dynamic-programming notes emphasize naming subproblems, relating them recursively, ordering dependencies, defining base cases and recovering the desired solution. They also describe parent pointers when the actual solution is needed. MIT DP subproblem notes
For a different task, capacity alone may be insufficient state. Exact weight, limited item counts, order-sensitive choices or additional constraints change what history matters. If two situations share a state label but permit different future choices, the state definition has probably discarded information it needs.
Derive the transition from the choice
For the next item, either skip it or take it if its weight fits. The full recurrence compares the previous prefix's value at c with its value at c minus the item's weight plus the item's value. Both candidates must refer to the correct earlier prefix to preserve the 0/1 rule.
Base values of zero fit this at-most-capacity problem with the option to choose nothing. An exact-weight variant needs an unreachable-state representation instead of treating every capacity as already achievable with zero value. Reusing the same initialization can silently change the problem.
This is an editorial derivation framework. It does not imply that every optimization problem admits a small or efficient DP state space.
Evaluation order is part of the algorithm
In the compressed implementation, dp[c] begins an item iteration as the answer for the previous item prefix. Descending c ensures dp[c-weight] has not yet incorporated the current item. Ascending order would allow the current item to contribute repeatedly and would solve a different recurrence.
Explain that invariant rather than memorizing a loop direction. Other problems and dependencies require other orders. Top-down memoization can also be appropriate when it visits a useful subset of states, but recursion depth and cache identity still need attention.
Reconstruct before discarding history
With a full table, walk backward from the final state. Compare the chosen value with the previous-prefix alternative under a declared tie rule; when an item is taken, record it and reduce capacity before moving to the earlier prefix. Verify the reconstructed total weight and value.
A one-row value array does not retain that complete history. A separate choice structure or persistent predecessor representation may preserve it, but it needs its own correctness argument. Naively overwriting one predecessor per capacity can create a chain inconsistent with the iteration that produced the optimum.
Best Practices
Begin with the clearest correct state and recurrence before compressing memory. Test a small full-table or brute-force reference, then compare the optimized implementation on small exhaustive cases. The article's checker uses an exhaustive subset oracle for the declared item set and several capacities.
Choose cases that distinguish similar problems. A single item with capacity for two copies distinguishes 0/1 from unbounded behavior. An exact-fill case distinguishes feasible zero from unreachable. Ties matter when the returned solution must be deterministic or satisfy a secondary criterion.
State complexity in terms of all relevant dimensions. The one-row example uses O(C) storage and O(nC) work for n items and integer capacity C. Because C is a numeric value rather than its encoding length, that bound is pseudopolynomial; it can be impractical for very large capacities even when there are few items.
Preserve representation assumptions. Scaling fractional weights to integers can increase the state space and may alter the problem if done approximately. Large objective values, invalid capacities and unsupported input types require a separate validation contract in production code.
Test reconstructed solutions independently if the application needs them. Check selected identities, total weight, no repeated item and agreement with the reported value. Passing a value-only test cannot establish a valid reconstruction path.
Reverse a memory optimization when it obscures dependencies or loses required output. A larger table can be the right engineering choice for a small bounded input. Conversely, compress when the dependency proof and output requirements support it, rather than keeping history only out of habit.
Common Mistakes
Writing the table before defining the state
Changing loop direction without rechecking the invariant
Initializing impossible states to zero
Returning only the value when callers need the solution
FAQ
Why does capacity run downward?
So the current item reads values from the previous item iteration. In this 0/1 recurrence, upward iteration can reuse the same item. The direction follows the dependency meaning.
Does this function return the chosen items?
No. It returns only the optimum value. A complete item-selection result needs preserved choice history or another correctly designed reconstruction method.
Is O(nC) always efficient?
No. C is the numeric capacity, so it may be very large relative to the input's encoding length. Assess the actual constraints and state count before choosing the method.