Specials
Specials Burst Balloons - Reverse Trick Problem: Bursting elements changes adjacency, breaking subproblem independence.
Archive
Pointer DP
Ugly Number II nth number where it only has prime factor 2, 3 or 5. You can obviously bfs via a set or pq. The dp pointer way has no log factor.
Segment DP
aka segmentation dp this is prefix dp as opposed to internal dp because we operate on prefixes ( rather than intervals — any arbitary split that is not a prefix ) a ggeneral sementation dp is optimising something over segments.
Cycles
cycle detection ( generic ) the general way to do is use a visited enum with 3 states.
Specials
word ladder The obvious O(n^2 * word len) exists. The tricky idea to assign the same node id to wildcard patterns.
Topological Sort
toposort say toposort if a function [sorted nodes] = f(G) s.t.
Postorder Merge
postorder merge instead of building the result, as we go down, we build it POST order as in after the rec step this is very similar to DP except since you are only dependent on children states you usually optimise globally and return NEEDED state problems maximum path sum on a binary tree f(u) → max...
Base Monotonic Deque
Base Monotonic Deque When To Use Use this when you need the best max/min candidate among active indices. The deque stores indices.
Base Monotonic Stack
Base Mono Stack When To Use Use this when each index needs the nearest greater/smaller element on one side.
DP Window Optimisation
DP Window Optimisation When To Use Use this when a DP transition asks for min or max over a moving valid range.