Specials
Specials Median of Two Sorted Arrays Two ways: k/2 elimination, or binary search the cut size in the smaller array until the boundary condition holds.
Archive
Core Idea
Interval DP Core: optimal solution for [i, j] is f(some continuous split of the interval).
Problems
Interval DP Problems Shared Boundary (Points / Coordinates) 1547. Minimum Cost to Cut a Stick 312. Burst Balloons 1039.
Specials
Specials Burst Balloons - Reverse Trick Problem: Bursting elements changes adjacency, breaking subproblem independence.
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...