DSA & Algorithms
Part 10 of 16 · DSA Advanced & Company FavoritesDP Advanced - State machine DP, Digit DP intro, Interval DP, Bitmask DP
State-machine DP, digit DP intro, interval DP, and bitmask DP for harder company rounds.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
One index is not enough state
Prefer
Add a phase, a span, or a mask
State-machine, interval, bitmask, and digit DP are the four extensions.
- Cooldown profit needs hold, sold, and rest.
- Interval DP fills by length.
- A mask fits when n is at most 20.
Alternative
Add another nested loop and hope
The recurrence is wrong if the cell does not name its extra state.
- You reuse a 0/1 loop for a state machine.
- You fill interval DP by the wrong length order.
- You bitmask n = 40.
Name the extra state
Phase, span, or mask.
- 1
Write the cell meaning
Include the phase or the mask in the sentence. - 2
Order the loops
Length for intervals. Bits for masks. - 3
Check n
Masks stop being interview-sized past about 20.
Overview
State-machine DP, digit DP intro, interval DP, and bitmask DP for harder company rounds.
When companies ask this
Recognition cues: stock buy/sell with states; burst balloons / matrix chain; TSP-like n≤20; digit constraints on numbers; palindrome partitioning DP.
Deepens wave-1 dsa-dp-1d and dsa-dp-2d-knapsack-grid.
Mental model
Decisions
- 1
1. Start from 1D or 2D
- next2. What extra state?
- ?
2. What extra state?
- phase3. State machine
- span4. Interval or mask?
- 3
3. State machine
- ?
4. Interval or mask?
- interval5. dp of i, j
- mask6. Bitmask or digit DP
- 5
5. dp of i, j
- 6
6. Bitmask or digit DP
Lesson map
DP Advanced - State machine DP, Digit DP intro, Interval DP, Bitmask DP
State-machine DP, digit DP intro, interval DP, and bitmask DP for harder company rounds.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB classic["1. Start from 1D or 2D"] kind["2. What extra state?"] sm["3. State machine"] span["4. Interval or mask?"] classic -->|1. Start from 1D or 2D| kind kind -->|phase| sm kind -->|span| span
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- State machine O(n); interval O(n^3); bitmask O(2^n n^2) TSP.
- Pitfalls: wrong transition order; not padding balloons with 1; revisiting bits in mask.
Interviewer traps
LeetCode drill (real problems)
- Best Time to Buy and Sell Stock with Cooldown
- Best Time to Buy and Sell Stock with Transaction Fee
- Burst Balloons
- Minimum Cost to Merge Stones
- Palindrome Partitioning II
- Partition Equal Subset Sum
- Shortest Path Visiting All Nodes
- Number of Ways to Wear Different Hats to Each Other
- Count Numbers With Unique Digits
YouTube
Interview Q&A
State machine DP?
Answer
Explicit states (hold/sold/rest) + transitions.
Interval DP order?
Answer
Increasing length; enumerate split k.
Bitmask when?
Answer
n≤20; state = visited set.
Digit DP idea?
Answer
Digits from MSB; tight flag; memo pos/tight/mask.
Burst balloons pad?
Answer
Virtual 1s at ends so edges score.
Related wave-1?
Answer
dp-1d, dp-2d, bit-manipulation.
Shortest path all nodes?
Answer
BFS state (node, mask).
Stock fee vs cooldown?
Answer
Fee on sell; cooldown forces rest day.