Core pattern
Interval / Advanced DP
Step 9 of 14Pattern 7 of 7
×How to recognize it fast
Use this bucket when forward simulation feels impossible and you need to think in ranges, trees, or used-state masks.
When you see
choose split pointburst order matterspalindrome rangesubarray interval answertree constraintsused set matters
Think
- Should this be dp[left][right] on a range?
- Should recursion return take / skip states from a tree?
- Should used elements become a bitmask?
What to do once the pattern is clear
Core trick
- Range DP: dp[l][r] is the answer for an interval.
- Tree DP: return multiple states from each node, usually take and skip.
- Bitmask DP: the used-set becomes part of the state.
Shortcut recognition
Order is awkward going forwardThe answer depends on a subarray rangeA tree or used-set is part of the state
Hidden trick
Burst Balloons becomes much easier when you choose the last balloon to burst instead of the first. That one mindset shift turns an ugly problem into clean interval DP.
Range DP idea
dp[l][r] = best answer inside the interval [l, r]