Bitmask DP

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.

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.