state 29 of 32 · 5 min
What a table costs, and when it will not fit
The complexity of a dynamic programming solution is nearly always the same product, and reading it off the state tells you whether the approach is viable before writing anything.
The formula
time = (number of states) x (work per state)
space = (number of states), or less if rolled| Problem | States | Per state | Time |
|---|---|---|---|
| Fibonacci | n | O(1) | O(n) |
| Knapsack | n x C | O(1) | O(nC) |
| LCS | n x m | O(1) | O(nm) |
| Interval | n squared | O(n) split points | O(n cubed) |
| Bitmask TSP | 2^n x n | O(n) | O(2^n n squared) |
Working this out first is the cheapest useful thing you can do. A state space of 10^12 is not worth implementing.
Pseudo-polynomial
Knapsack is O(nC), which looks polynomial and is not polynomial in the input size.
The capacity C is written in about log C bits, so the running time is exponential in the number of bits. That is why subset sum and knapsack are NP-complete while having table solutions, and it is a distinction interviewers listen for.
The practical consequence: 100 items with capacity 10 million is a billion cells, and the item count being small does not help.
When the table will not fit
Change the axis. If the values are small and the weights are large, index by value instead: best[i][v] is the least weight achieving value v. Same problem, and the dimension you pick is whichever bound is small.
Roll it. Removes a factor, costs reconstruction.
Memoise instead. If the reachable states are a tiny fraction of the possible ones, top down computes only those. Coin change with a large target and few denominations is the standard case.
Accept approximation. Knapsack has a scheme that trades a guaranteed bound on error for polynomial time, by rounding the values.
Reconsider the tool. Sometimes the problem has a greedy rule, a formula, or a flow formulation that is genuinely faster.
Reading the constraints
The bound in a problem statement is usually telling you the intended complexity:
n <= 20 exponential: bitmask, subsets
n <= 500 O(n cubed): interval DP
n <= 5,000 O(n squared): two sequence grids
n <= 100,000 O(n log n) or O(n): linear DP, greedyA problem giving n <= 100,000 and a target of 10^9 is telling you the answer is not a table over the target.