Four shapes of a DP state
This is the last of the four DP chapters. So far the state has been a plain dp[i] or dp[i][j]. Here it takes four new shapes: a machine, an interval, a tree, and a set. The routine does not change: define the state, write the transition by looking at the last step, then fix the order in which the table is filled. What changes is what the state looks like.
From one table to four shapes of state
Advanced DP is not a new method. Only the shape of the state changes.
Look back at the three DP chapters so far. Chapter 07 used dp[i] along a line. Chapter 08 used dp[i][j] for knapsack and grids, with two dimensions. Chapter 09 used a two-dimensional table comparing two strings. In all of them the state fits in one sentence and is located by one or two indices. In this chapter the questions get harder, and the state itself grows a structure.
The problem moves between a few named situations: holding, in cash, in cooldown. Each situation is one state, and the transitions are the legal moves between them. Signal: at any moment you are in one of a few modes, and there are clear rules for switching. The main example is the stock trading family.
dp no longer walks along an array. It follows the parent-child links: children are computed first and combined upward, which is a post-order traversal. Signal: the problem is defined on a tree, and a node's answer is built from its children's answers. Examples: House Robber III, the diameter of a binary tree.
dp[i][j] is the best value for the interval from i to j. Its transition reads only strictly shorter intervals, so every shorter interval has to be computed first. In the table that means filling one diagonal at a time. Signal: an operation merges or splits a run of adjacent items. Examples: Burst Balloons, longest palindromic subsequence.
The binary digits of one integer record which elements are already used, so dp[mask] is the best value for using exactly that set. Signal: n is surprisingly small (about 20 or less) and the state has to remember a set. The groundwork is bit manipulation in Chapter 04. Examples: Beautiful Arrangement, the traveling salesman problem.
All four use the same five steps
Four types sounds like four things to learn, but they all follow the five steps from Chapter 07: define the state, split by the last step, set the base cases, fix the iteration order, and check a small example by hand. The only new work is recognising what shape the state should have. A few switching situations means a state machine. A tree means tree DP. Merging or splitting an interval means interval DP. A small n plus a set means bitmask. Once the shape is right, the transition usually follows from the same question as always: what was the last step?
State machine DP: one diagram for the whole stock family
MEDIUMWorked example · LC 309 with a cooldown: holding, in cash, and in cooldown, day by day
The buy-and-sell-stock problems on LeetCode are one family: the same core with one more condition added each time. Rather than memorising them separately, learn the model they share, a state machine. At the close of any day you are in one of a small number of situations, and tomorrow's situation is decided by today's situation plus today's action. Draw the situations as boxes and the legal actions as arrows. The DP then grows the best profit inside each box, one day at a time.
One buy and one sell
Adds: nothing yet. Keep the lowest price seen so far; the answer is the largest value of price − lowest so far. This is where the family starts.
Unlimited trades
Adds: two states, hold and cash, which convert into each other any number of times. A greedy rule also works here (take every rise) and gives the same answer, but the state machine version is the one that survives the next conditions.
At most k trades
Adds: the number of trades already used becomes part of the state. LC 123 is the case k = 2, which needs four running values. LC 188 is the general dp[k][hold], costing O(nk).
A one-day cooldown (worked example below)
Adds: one new state, sold, meaning you sold today. After a sale you must wait a day before buying, and two states cannot express that gap.
A transaction fee
Adds: no new state. Subtract the fee in the selling transition. It does break the LC 122 greedy rule, because many small trades each pay the fee, so from here on the DP is what you rely on.
Start from the smallest core, LC 122 with unlimited trades: two states and two transitions. Every later stock problem adds states or edits transitions on top of this shape.
sum(max(0, b - a) for a, b in zip(prices, prices[1:])). The state machine version extends to LC 714 and LC 309 without changing shape. The one-liner does not.Problem (LC 309): you may trade any number of times, but you may not buy on the day right after a sale. Why are two states not enough? Because "I sold today" and "I have been in cash for a while" allow different actions tomorrow: the first may not buy, the second may. They have to be different states. So the empty-handed case splits into sold (just sold, blocked) and rest (in cash, free to buy). Three states, three transitions. Watch them move day by day:
Now translate the three arrows into code. The one thing to watch: all three new values must be computed from yesterday's values. Either use temporary variables, or use an assignment form that evaluates the whole right-hand side before assigning.
Complexity and follow-up questions
Time O(n), space O(1). Follow-ups: (1) With a fee (LC 714), subtract it in the selling transition; two states are still enough. (2) At most k trades (LC 188): make the trade count a dimension, dp[k][2], for O(nk) time. (3) Why does a one-day cooldown need only one new state, instead of storing how many cooldown days are left? Because the wait is exactly one day, so "sold today" already says everything about what tomorrow allows. If the wait were m days, the remaining cooldown would have to go into the state. More conditions means more states or more dimensions, and that is what makes state machine DP easy to extend.
State machines outside practice problems
The "state plus transition" idea in these stock problems is a finite state machine, and it is used widely. A TCP connection moves through CLOSED, SYN_SENT, and ESTABLISHED. An order moves through awaiting payment, paid, shipped, and complete. A regular expression engine matches text by moving between states. A screen in an application is loading, loaded, or failed. Learning to break a situation into a fixed set of states with explicit transitions is useful well beyond practice problems.
Tree DP: take or skip, moved onto a tree
MEDIUMWorked example · LC 337 House Robber III: post-order, and every node reports two values
In Chapter 07, House Robber (LC 198) is a row of houses and dp[i] only looks at the previous cell. Now put the houses on a binary tree (LC 337): if you take a node, neither of its children may be taken. "The previous cell" of the array becomes "the two children". The direction of the transition changes from looking left along an array to asking downward along the tree.
The key point: each node must report two numbers to its parent, not one. Say clearly what the recursive function promises to return: dfs(node) returns [rob, skip] for the subtree at node, where rob is the best total when node is taken and skip is the best total when node is not taken. The parent needs both. If it takes itself, both children must be skipped, so it needs their skip values. If it skips itself, each child chooses freely, so it needs max(rob, skip) for each. A single max does not contain the skip value, so the parent could not combine the answers. Post-order traversal — recurse into both children first, then compute the node — is what produces the values bottom-up:
(take, skip) is the natural way to report two values. max(dfs(root)) then takes the larger of the two elements in one call.Tree DP where the return value is not the answer. dfs returns the number of nodes on the longest downward path from the node, while at each node it also updates a separate best-so-far variable with left depth + right depth. That sum counts edges, which is what the problem asks for. Returning one quantity and updating another is the standard shape, and LC 124 (maximum path sum) is identical.
Each node returns one of three codes: not watched, watched, or has a camera. Bottom-up, plus a greedy choice: delay every camera to the parent of an uncovered node, because one camera there covers the node, its siblings, and its own parent. Tree DP and greedy combined. Harder than the main line; come back to it later.
Two common mistakes in tree DP
(1) Returning a single value. A common first attempt is to have dfs return "the largest amount obtainable in this subtree". Then, when the parent wants to take itself, the child's skip value is gone. An incomplete state makes the transition wrong. (2) Using the wrong traversal order. It must be post-order, with the children computed first. Pre-order or level order would use a child's value before that value exists, which breaks the rule that every value a transition reads must already be final.
Interval DP: a long interval stands on shorter ones
HARDWorked example · LC 312 Burst Balloons: reason backwards, then fill by increasing interval length
Problem (LC 312): a row of balloons each holds a number. Bursting balloon i gives left × nums[i] × right coins, where left and right are its current immediate neighbors. After a balloon bursts, its two neighbors become adjacent. Find the largest number of coins from bursting every balloon.
Why does forward reasoning get stuck? If you enumerate which balloon to burst first, the two remaining halves merge into one new row, so they affect each other. The subproblems are not independent, and there is no clean state to define. This is the classic trap of interval DP.
Reasoning backwards: enumerate the balloon k that is burst last instead. When k is burst, every other balloon in the interval (i, j) is already gone, so k's neighbors are exactly the endpoints i and j, which gives arr[i] × arr[k] × arr[j]. Everything to the left of k, and everything to the right of k, was burst earlier and never interacted, so (i, k) and (k, j) are independent subproblems. That gives:
dp[i][j] = max over k∈(i,j) of ( dp[i][k] + arr[i]×arr[k]×arr[j] + dp[k][j] )
Pad both ends with a balloon of value 1 so the endpoints always exist and no boundary case is needed. Every cell the transition reads — dp[i][k] and dp[k][j] — is a strictly shorter interval than (i, j). So all shorter intervals must be filled first, and filling by increasing interval length is how you guarantee that. In the table it looks like moving along one diagonal at a time. The order is not a convention; it is what the dependency requires. Step through the table:
1
3
1
5
8
1
1
3
1
5
8
1
arr = [1] + nums + [1] adds both padded balloons in one line. The length starts at 2 because an interval shorter than that holds no balloon and its dp value stays 0.Two shapes of interval transition: shrink from both ends, or pick a split point
An interval transition is usually one of two shapes. (1) Shrink from both ends: compare s[i] with s[j] and move inward, as in LC 516 longest palindromic subsequence, where s[i] == s[j] gives dp[i+1][j−1] + 2. Chapter 09 solved that one as an LCS; here it is the interval view of the same problem. (2) Pick a point k inside (i, j) — a split point, or the last step — as in Burst Balloons, merging stones, and matrix chain multiplication. Both shapes share the same consequence: a long interval depends on shorter ones, so fill by increasing length.
Complexity and follow-up questions
Time O(n³): there are O(n²) intervals and each one tries O(n) choices of k. Space O(n²) for the table. The table cannot be reduced to a single row here, because the transition reads dp[i][k] from the same row and dp[k][j] from another row, not only from the previous diagonal. Follow-ups: (1) "Why the last balloon and not the first?" Only fixing the last one keeps the two sides independent; going forward makes the intervals merge. This is the heart of the problem, so answer it. (2) "What are the padded balloons for?" They make the neighbors of the edge balloons always exist, with value 1, which removes a lot of boundary handling. (3) "Can it be memoised instead?" Yes: top-down dfs(i, j) with a memo table has the same complexity and is often easier to write.
Bitmask DP: a set stored in one integer
MEDIUMLC 526 Beautiful Arrangement, built on "bits as a set" from Chapter 04
In some problems the state is naturally a set: which elements have already been used. A set of n elements has 2ⁿ subsets. When n is small, about 20 or less, you can store the subset in the binary digits of one integer: bit b is 1 when element b has been used. This is called bitmask DP, or state compression. The groundwork is Chapter 04, where an int is treated as a row of switches. Try the correspondence between a set and an integer first:
Problem (LC 526): place 1..n into n positions. If every position i (counting from 1) satisfies perm[i] % i == 0 or i % perm[i] == 0, the placement is a beautiful arrangement. Count them. Brute force: generate all n! permutations and check each one, which is far too slow at n = 15. Bitmask: what matters about the past is only which numbers are already used, not the order they went in, and n ≤ 15. So let mask be the used set. Then popcount(mask) is the number of filled positions, call it pos, and the next position to fill is pos+1. Try every unused number that is compatible with pos+1. There are 2ⁿ masks and each tries n numbers, so the cost is (number of subsets) × (work per subset) = O(2ⁿ × n) time and O(2ⁿ) space.
bin(mask).count("1") counts the 1 bits. Python 3.10 and later have the faster mask.bit_count(). dp[-1] is the last entry, the mask with every bit set.The ceiling of bitmask DP: the traveling salesman problem
The best known use of bitmask DP is the traveling salesman problem: visit n cities once each, along the shortest route. The state is dp[mask][i] = the shortest distance for a route that has visited exactly the cities in mask and currently stops at city i. There are 2ⁿ·n states and each one tries n next cities, so the cost is O(2ⁿ × n²) instead of checking n! routes. That is still exponential, but it solves instances up to about n = 20, which is enough for real tasks such as planning a delivery route or ordering the drill holes on a circuit board. This is the boundary of bitmask DP: n must be small, but a small n can still be worth a lot.
Where bitmask DP stops working
Seeing a set is not enough; check n first, because the table has 2ⁿ entries and has to fit in memory. n ≤ 20 is comfortable: 2²⁰ is about one million. n = 25 is 33 million and n = 30 is about one billion, which is out. This is why a bitmask problem almost always comes with a surprisingly small n in its constraints. It is both the hint and the limit.
One step further: digit DP and probability DP
Recognising the signal is enough here. Neither is required, and both are rare in interviews.
Two more areas of DP are worth naming. Both follow fixed patterns but need more background than this chapter assumes. For now it is enough to know they exist and recognize the signal, and to read more when you actually meet one.
Signal: count the integers in a range [L, R] whose digits have some property (no digit 4, strictly increasing digits, a given digit sum). State: which digit position you are at, a flag saying whether the digits chosen so far still match the bound exactly, and whatever else the property needs. That flag is usually called tight, and it is what keeps the count inside the numeric bound: while it is true, the current digit may not exceed the bound's digit at this position; once you place a smaller digit it becomes false and all later positions are free. Search from the most significant digit down, with memoisation. Example: LC 233 Number of Digit One.
Signal: the question asks for a probability, or for the expected value of some quantity. Transition: instead of adding counts, add the branches weighted by their probabilities. Watch out: an expected value often has to be computed backwards, from the final states toward the start, because "the expected value so far" cannot be defined usefully going forward. Examples: LC 688 Knight Probability in Chessboard, LC 837 New 21 Game.
You have now covered the whole DP range
From the one-line idea in Chapter 07 — store a result so you can reuse it — through the linear table, the knapsack capacity table, and the two-sequence table, to the state machine, tree, interval, and set of this chapter, you now have a full routine: recognize the shape of the state, then apply the five steps. Digit DP and probability DP are two smaller areas at the edge. DP is not mysterious. It writes out how decisions and states develop, one cell at a time.
Problem set: 12 advanced DP problems
Main line + advancedGrouped as state machine, tree, interval, bitmask, and optional. Think for 30 seconds before opening the hint.
Quiz
✎ QuizAll 7 correct turns this chapter green, and finishes the DP series.
LC 309 (with cooldown) needs one more state than LC 122. What does that extra state represent?
In LC 337 (House Robber III), why does each node return the pair [rob, skip] instead of just "the largest amount obtainable in this subtree"?
Why does interval DP (LC 312, LC 516) fill the table in order of increasing interval length?
LC 312 is modelled by enumerating the balloon k that is burst last. Why last and not first?
Which features of a problem suggest bitmask DP (state compression)? (Select all that apply)
For LC 122 (unlimited trades), which statement about the greedy solution and the state machine DP is correct?
Tree DP exercise. The binary tree is [3, 4, 5, 1, 3, null, 1]: the root is 3, its children are 4 and 5, the children of 4 are 1 and 3, and 5 has a right child 1. Following the rules of House Robber III, what is the largest amount you can take?
- Advanced DP changes the shape of the state, not the routine: a situation (state machine), a node on a tree, an interval [i, j], or a set. Get the shape right and the transition usually follows.
- State machine DP: the problem moves between a few named situations, and each new condition adds a state or a dimension (LC 121 → 122 → 123 → 309 → 714). A cooldown adds the state sold, meaning "sold today".
- Tree DP: post-order, bottom-up, and every node reports more than one value ([rob, skip] in LC 337). Say what the recursive function promises to return. Often the return value is not the answer (LC 543 returns a depth and updates a diameter).
- Interval DP: dp[i][j] reads strictly shorter intervals, so fill by increasing interval length — one diagonal at a time. The hard part is usually choosing the split point or the last step k (in LC 312, the balloon burst last).
- Bitmask DP: the bits of one integer are a set, and dp[mask] is the best value for using exactly that set. The practical limit is n ≤ 20, so that 2ⁿ fits.
m & (m - 1)clears the lowest set bit;m & -misolates it. - "What was the last step?" opens every DP: which cell did the last one come from (linear), take the last item or not (knapsack), which balloon was burst last (interval), which number was placed last (bitmask).
- Complexity is always (number of states) × (work per transition), and the table counts in the space before any reduction. Recognising digit DP and probability DP is enough. The four DP chapters end here.