The idea
Dynamic programming applies when the answer can be built from answers to smaller versions of the same problem, and those smaller versions repeat. Computing each one once and storing it turns exponential search into a table fill.
Every DP is five decisions: what a state means (f[i] = …), the base cases, the transition from smaller states, the order to fill them in, and where the answer is.
The running time is the number of states times the cost of one transition.
Sample problem
746. Min Cost Climbing Stairs ↗ Easy
cost[i] is the price of stepping off stair i, after which you climb one or two stairs. Starting from stair 0 or 1, return the minimum cost to get past the last stair.
cost = [1,100,1,1,1,100,1,1,100,1] output = 6
Why the solution works
Trying every way to climb doubles the work with each stair. But the cheapest way to reach stair i only depends on the cheapest ways to reach stairs i−1 and i−2: whatever happened before those does not matter.
So define the state f[i] = minimum cost to stand on stair i, the base cases f[0] = f[1] = 0, and the transition f[i] = min(f[i−1] + cost[i−1], f[i−2] + cost[i−2]). Fill it left to right; the answer is f[n].
That is all of dynamic programming: each subproblem is solved once and reused.
Complexity: O(n) time and memory (two variables would be enough).
Watch out
- Write the meaning of the state in words before any code. Most wrong DPs have a vague state.
- Fill states in an order where everything a transition reads is already computed.
- Initialise minimisations with a large value and maximisations with a very small one, and watch for overflow when adding to them.