Concepts9
Reinforcement Learning Theory
Reinforcement Learning (RL) studies how an agent learns to act in an environment to maximize long-term cumulative reward.
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.”
Partition Function
The partition function p(n) counts the number of ways to write n as a sum of positive integers where order does not matter.
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.
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.
Aho-Corasick - DP Applications
Aho–Corasick (AC) turns a set of forbidden patterns into a finite automaton that lets you process or generate strings while tracking whether any pattern appears.
Palindromic Tree (Eertree)
A Palindromic Tree (Eertree) stores every distinct palindromic substring of a string as a node and can be built online in linear time.