Concepts24
State Space Reduction
State space reduction shrinks the number of dynamic programming or search states by keeping only the information that truly affects future decisions.
DP on Broken Profile - Plug DP
Plug DP (DP on broken profile with plugs) sweeps a grid cell by cell while remembering how partial path segments cross the frontier as labeled “plugs.”
Matrix Exponentiation
Matrix exponentiation turns repeated linear transitions into a single fast power of a matrix using exponentiation by squaring.
Broken Profile DP
Broken Profile DP is a dynamic programming technique that sweeps a grid one cell or one column at a time while encoding the boundary between processed and unprocessed cells as a compact state.
Exchange Arguments in DP
An exchange argument proves that any optimal solution can be reordered to satisfy a simple sorting rule by showing that swapping adjacent out-of-order elements never helps.
Knuth Optimization
Knuth Optimization speeds up a class of interval dynamic programming (DP) from O(n^3) to O(n^2) by exploiting the monotonicity of optimal split points.
Digit DP - Advanced States
Digit DP counts integers in a range by scanning digits from most significant to least while maintaining compact state information.
DP with Probability
DP with probability models how chance flows between states over time by repeatedly redistributing mass according to transition probabilities.
Interval DP
Interval DP solves problems where the optimal answer for a segment [i, j] depends on answers of its subsegments.
Tree DP - Rerooting Technique
Rerooting (a.k.a. 换根 DP) computes a per-node answer as if each node were the root, in total O(n) time on trees.
Digit DP
Digit DP is a dynamic programming technique for counting or aggregating values over all integers in a range that satisfy a digit-based property.
Tree DP - Matching and Covering
Tree DP solves matching, vertex cover, and independent set on trees in linear time using small state transitions per node.