Dynamic Programming

Iterating over all subsets of every subset of an `n`-element set sounds like `4^n` work. The actual cost is `3^n`: each element is in three states (in the outer mask only, in both, or in neither), and the binomial theorem collapses the sum. Insights like that turn what looks like a complexity wall into a tight, elegant solution. **Advanced Bit Manipulation** collects those insights. You will generate Gray codes (adjacent values differ by one bit, used in error correction), enumerate all subsets of a bitmask via the `for (s = mask; s > 0; s = (s - 1) & mask)` template, and master bit tricks like isolating the lowest set bit with `x & -x`, turning it off with `x & (x - 1)`, counting trailing zeros, and swapping without a temp variable. The lesson also covers advanced XOR applications (range XOR, two missing numbers, XOR basis over GF(2)) and bitwise DP including profile DP for grid tiling. In **Bit Manipulation (Intro)**, you mastered the basic operators and the single-number XOR trick. This lesson treats bits as a full algorithmic medium. Next, **Complexity & Proof Intuition (Optional)** revisits the theoretical foundations behind everything built so far.

Edit distance, the minimum number of insertions, deletions, and substitutions to turn one string into another, is what every spell checker quietly computes when it suggests a correction. The DP table that solves it has `m * n` cells, each filled by looking at three neighbors. That single 2D recurrence is the gateway to a much larger family: longest common subsequence, knapsack, palindrome partitioning, regex matching, and many more. **Dynamic Programming (Advanced)** is where 1D DP graduates into the rest of the field. You will work through 2D grid and string DP (unique paths, edit distance, LCS, longest common substring), the knapsack family (0/1, unbounded, subset sum, coin change), sequence DP (LIS in `O(n^2)` and the patience-sorting `O(n log n)` variant, maximum product subarray, word break), string DP (palindromic subsequence and substring, regex and wildcard matching), DP on trees (diameter, max path sum, binary tree cameras), interval DP via matrix chain multiplication, and an introduction to bitmask DP for TSP and assignment problems. In **Dynamic Programming (Intro)**, you learned to define state, transition, and base cases on linear problems. This lesson layers a second dimension onto each. Next, **Advanced DP Techniques** introduces optimization tools that push DP beyond standard tabulation.

Naive recursive Fibonacci computes `fib(40)` in seconds, `fib(50)` in minutes, and gives up on `fib(60)`, all because it recomputes the same subproblems exponentially many times. Cache the result of each `fib(k)` the first time you compute it and the same recursion runs in linear time. That single change, remembering answers, is the entire content of dynamic programming. **Dynamic Programming (Intro)** turns that observation into a complete problem-solving framework. You will identify overlapping subproblems and optimal substructure (the two properties a problem must have for DP to apply), and master both approaches: top-down memoization (recursion plus a cache) and bottom-up tabulation (iteratively filling a table). Classic 1D problems include Fibonacci, climbing stairs, coin change, house robber, and a first look at Kadane's algorithm. The lesson teaches you to define state precisely ("what does `dp[i]` represent?"), write the transition ("how does `dp[i]` follow from earlier states?"), set base cases, and apply rolling-variable space optimization that drops `O(n)` to `O(1)`. In **Recursion Fundamentals**, you treated each recursive call as a stack frame. Memoization just attaches a cache so identical inputs return immediately. Next, **Bit Manipulation (Intro)** turns to a different toolkit, where bitwise operators give elegant `O(1)` solutions.

Standard tabulation gets you `O(n^2)` DP. The Convex Hull Trick brings the same recurrence down to `O(n log n)` whenever the transition is a linear function of the previous state, and the speedup matters: contest problems with `n = 10^5` go from too-slow to fast enough on exactly that change. A whole sub-field of DP is dedicated to these recurrence-shaped optimizations, and this lesson is your entry into it. **Advanced DP Techniques** covers four directions of post-tabulation DP. Optimization methods include the Convex Hull Trick (offline sorted-slope and online Li Chao tree), Divide and Conquer DP for monotone-split problems, and Knuth's Optimization for optimal-BST-style recurrences. Digit DP teaches you how to count numbers with properties in a range `[L, R]` by carrying a tight-constraint flag through the recursion. Advanced bitmask DP solves TSP, Hamiltonian path, and grid-tiling profile DP. Probability DP turns recurrences over expected values into clean tables, and Kadane's algorithm generalizes to circular and 2D variants. In **Dynamic Programming (Advanced)**, you mastered multi-dimensional state and transitions. This lesson asks the next question: when the table is too big or the transition too slow, how do you optimize? Next, **Graph Algorithms (Advanced)** brings similar depth to graph theory.

Two players take turns removing stones from piles, the player who takes the last stone wins, and the entire winning strategy boils down to one calculation: XOR all pile sizes together, and you win if and only if the result is non-zero. That is Nim, and the surprise is not that it has a strategy but that the strategy is so compact. The Sprague-Grundy theorem extends the same idea to every impartial combinatorial game. **Game Theory** introduces the algorithmic side of two-player game analysis. You will work through Nim and its XOR strategy, then see how the Sprague-Grundy theorem assigns a Grundy number (nimber) to every position and how XOR-of-nimbers solves any sum of games. The lesson then moves to general game trees: minimax for optimal play, alpha-beta pruning for cutting branches that cannot affect the result, and move ordering for better pruning. You will analyze game states using DP, classifying positions as winning or losing by computing backward from terminal states, and meet retrograde analysis as a complete-game-state technique. In **Dynamic Programming (Intro)**, you learned to recurse on subproblems and cache results. **Recursion Fundamentals** gave you the call-stack model behind minimax and Grundy computation. Game theory recasts those tools as adversarial search. Next, **Randomized Algorithms** turns to a different way of taming worst-case inputs.