Algorithms · advanced
Dynamic programming
Dynamic programming solves a problem by defining reusable states, a recurrence between them, base cases, and an evaluation order so each relevant state is computed once.
Why it matters
DP makes problems with overlapping subproblems tractable and provides a disciplined route from a recursive specification to predictable time and space bounds.
Mental model
How to reason about dynamic programming
A state is the smallest summary of the past needed to make future decisions. The transition combines already solved smaller states; table dimensions reveal how many states exist.
Analogy
A route planner records the best known cost to each checkpoint. Later routes build on those checkpoint costs instead of retracing every possible journey from the start.
Examples
See the boundary, not just the happy path
Worked example · Minimum coin count
dp[x] = 1 + min(dp[x-coin])State x represents the amount remaining or formed; each transition chooses a final coin and reuses a smaller solved amount.
Worked example · Compress storage
Fibonacci needs only the previous two table valuesWhen each transition reads a fixed recent frontier, older states can be discarded without changing the recurrence.
Useful contrast · Greedy is not automatically DP
choose the locally largest coin at every stepA local choice needs a proof of global optimality. DP instead compares all recurrence choices for each state.
Common mistakes
Misconceptions to remove early
Defining a state that omits future-relevant history
Two partial solutions may look identical under an underspecified state yet allow different futures, causing invalid reuse.
Writing a table before the recurrence
Dimensions and loops should follow from the state and dependencies. Starting with an arbitrary matrix often creates redundant work or wrong evaluation order.
Quick check
Can you predict the result?
1. What determines a dynamic program's state dimensions?
- • The minimal information needed to distinguish subproblems with different future answers
- • The number of loops the programmer prefers
- • The number of examples in the prompt
2. How do you estimate a typical DP's time complexity?
Keep building