Maximin and Minimax
Split Array Largest Sum ( greedy split ).
Archive
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.
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.