Concepts318
Category
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.
Sum over Subsets (SOS) DP
Sum over Subsets (SOS) DP lets you compute F[mask] = sum of A[submask] over all submasks in O(n 2^n) instead of O(3^n).
DP with Expected Value
Dynamic programming with expected value solves problems where each state transitions randomly and we seek the expected cost, time, or steps to reach a goal.
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.
LIS Variants
LIS variants extend the classic longest increasing subsequence to handle non-decreasing sequences, counting how many LIS exist, and maximizing the sum of a subsequence.
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.
Bitmask DP
Bitmask DP compresses the state of a subset of n elements into an integer mask, enabling elegant dynamic programming over all subsets.
Longest Common Subsequence
The Longest Common Subsequence (LCS) between two sequences is the longest sequence that appears in both, not necessarily contiguously.