Lesson 15 of 16 · 20:41
Dynamic programming
Dynamic programming applies when many paths lead to the same subproblem. Instead of solving that state repeatedly, compute it once and reuse the answer. The central task is not building a table; it is defining a state whose value has a precise meaning and whose dependencies are smaller or earlier states.
A reliable workflow is: write the brute-force choice recursion, identify the changing variables that determine future work, cache those variables, then choose whether to keep top-down recursion or order the states bottom-up.
What you should be able to do after this lesson
- Write the state meaning as a sentence
- Derive transitions from legal final choices
- Count states and transition work explicitly
The mental model
A DP table is a cache of answers to precisely defined subproblems. The recurrence says which already-solved states combine into the current one.
Recognize it when: DP is likely when choices create overlapping subproblems and the prompt asks for a count, minimum, maximum, or feasibility over prefixes, positions, capacities, or remaining resources.
The invariant to say aloud: Every memo or table entry equals the correct answer for the exact state definition, and every dependency is available before the state is finalized.
Learn the ideas one at a time
Concept 1 of 6
State
Watch from 0:00 ↗Choose the smallest variables that uniquely describe a reusable subproblem—often an index, prefix length, capacity, previous choice, or grid position.
A state contains exactly the information needed to determine the remaining answer. Too little merges situations with different futures; too much prevents reuse. Common dimensions include an index, remaining capacity, previous choice, or grid coordinate.
Walk through an example
In climbing stairs, dp[i] means the number of ways to reach step i. The exact path used to reach i does not affect future choices, so it does not belong in the state.
In an interview
Say “dp[...] means ...” before writing a recurrence. If the sentence is vague, table indices will become guesswork.
Concept 2 of 6
Transition
Watch from 0:00 ↗Express the state answer using smaller states: choose/not choose, come from top/left, or take the best among legal previous decisions.
A transition partitions solutions by a final or next decision and combines smaller state answers without overlap errors. For optimization use min or max; for counting use addition; for feasibility use boolean OR. Confirm that every valid solution appears and none is double-counted.
Walk through an example
To reach stair i, the final move came from i-1 or i-2, so dp[i] = dp[i-1] + dp[i-2]. These cases are exhaustive and disjoint by final jump length.
In an interview
Derive the formula in words from legal choices, then translate it to code. Do not begin by drawing an unexplained grid.
Concept 3 of 6
Base cases
Watch from 0:00 ↗Define the smallest states directly. Base values are part of the mathematical recurrence, not a patch to stop recursion.
Base values define the smallest subproblems and make the recurrence mathematically complete. They often encode an empty choice: there is one way to choose nothing to make sum zero, while an impossible positive sum with no items has zero ways.
Walk through an example
For stair counting, dp[0] = 1 represents one way to be at the starting point. That convention lets the recurrence naturally produce dp[1] and dp[2].
In an interview
Check bases against the exact state meaning, especially zero-length input and zero capacity. Avoid treating them as loop patches.
Concept 4 of 6
Top-down memoization
Watch from 0:00 ↗Write the recursive contract first and cache by state. It evaluates only reached states but pays recursion overhead and stack space.
Memoization starts with the recursive contract and caches results by state. Before solving, check the cache; after solving, store the answer. It evaluates only reachable states and closely follows the reasoning, but recursion depth and function overhead remain.
Walk through an example
A naive Fibonacci call solves fib(3) from both fib(4) and fib(5). Memoization stores fib(3) once, so later calls return immediately instead of rebuilding its subtree.
In an interview
Ensure the cache key contains every variable that changes the future answer and no irrelevant mutable object identity.
Concept 5 of 6
Bottom-up tabulation
Watch from 0:00 ↗Order states so dependencies are already computed. It removes recursion and often reveals that only one row or a few previous values must be stored.
Tabulation orders states so every dependency is already available. Once the dependency graph is visible, storage can sometimes shrink: if row i depends only on row i-1, earlier rows need not remain. The iteration direction matters for in-place knapsack-style updates.
Walk through an example
If dp[i] uses only dp[i-1] and dp[i-2], keep two previous values instead of an n-element table, reducing O(n) space to O(1).
In an interview
Explain evaluation order and why overwritten states will not be needed later. Space optimization without that proof is risky.
Concept 6 of 6
Complexity
Watch from 0:00 ↗Time is number of reachable states × work per transition; space is stored states plus any recursion stack. Count state dimensions explicitly.
DP time equals the number of reachable states multiplied by the work to compute one state. A table with n × capacity states and an O(1) transition is O(n·capacity); trying every next choice may add another factor. Space counts stored states plus recursion depth for top-down code.
Walk through an example
A memoized function with indices i and j each ranging over n has at most n² distinct states even if the uncached recursion tree has exponentially many paths.
In an interview
List state dimensions and their ranges, then state transition cost. This produces a defensible bound instead of “DP is polynomial.”
Before you call this lesson done
- Define the state sentence
- Prove the transition covers legal choices
- Set semantic base cases
- Count state ranges × transition work
