Om's Brain

Advanced Dynamic Programming

10 min read

0️⃣ Read This First

You only need these once the core nine (see the DP guide) aren’t enough.

These patterns are rarer in interviews — most DP questions are still 1D / knapsack / strings / grid. The value here is recognition: spotting “oh, the state is a bitmask” or “this is a game, so it’s minimax” and knowing the template. The thinking is identical — state, choices, combine, base case — only the state gets fancier.

Ordered most → least likely to show up in an interview.

1️⃣ Bitmask DP 🎭

💡 Signal: n is tiny (≤ ~20) and the natural state is “which subset have I used/visited”. Encode that subset as the bits of an integer mask.

State: dp[mask] (sometimes dp[mask][last]). Each bit i = “element i is used”. Transitions flip one bit on.

Partition to K Equal Sum Subsets — LC 698 🔥 💀

Split nums into k subsets of equal sum. dp[mask] = the amount already filled in the current (unfinished) bucket after using exactly the elements in mask.

// LC 698. Partition to K Equal Sum Subsets
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k) return false;                    // can't divide evenly
        int target = sum / k, n = nums.size();
        int full = (1 << n) - 1;
        vector<int> dp(1 << n, -1);                   // dp[mask] = fill of current bucket; -1 = unreachable
        dp[0] = 0;
        for (int mask = 0; mask <= full; mask++) {
            if (dp[mask] == -1) continue;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue;        // element i already used
                if (dp[mask] + nums[i] > target) continue;
                int next = mask | (1 << i);
                if (dp[next] == -1)
                    dp[next] = (dp[mask] + nums[i]) % target;   // %target auto-closes a full bucket
            }
        }
        return dp[full] == 0;                         // all used AND last bucket closed
    }
};
// TC: O(2^n * n)   SC: O(2^n)

The bitmask tells

“Assign everyone to something”, “visit all nodes” (TSP), “cover all cells”, with n ≤ 20. 2^20 ≈ 10^6 states is fine; 2^25 is not. If n is large, it’s not bitmask DP.

2️⃣ Tree DP 🌳

💡 Signal: the structure is a tree, and a node’s answer is built from its children’s answers. This is DP on a recursion that’s already there (the tree itself).

State: solve(node) returns everything the parent needs — often a small tuple of “best if I include this node” vs “best if I don’t”.

House Robber III — LC 337 🔥 📍

Rob a binary tree; you can’t rob a node and its direct child. Return {robThis, skipThis} from each node.

// LC 337. House Robber III   (TreeNode is provided by LeetCode)
class Solution {
public:
    // returns {rob this node, skip this node}
    pair<int,int> solve(TreeNode* node) {
        if (!node) return {0, 0};
        auto [lRob, lSkip] = solve(node->left);
        auto [rRob, rSkip] = solve(node->right);
        int robThis  = node->val + lSkip + rSkip;             // rob node => skip both children
        int skipThis = max(lRob, lSkip) + max(rRob, rSkip);   // skip node => children choose freely
        return {robThis, skipThis};
    }
    int rob(TreeNode* root) {
        auto [r, s] = solve(root);
        return max(r, s);
    }
};
// TC: O(n)   SC: O(h) recursion

Tree DP = post-order + return a tuple

Compute children first (post-order), then combine. The “memo” is implicit — each node is visited once. Same idea powers Binary Tree Maximum Path Sum, Diameter of Binary Tree, and Binary Tree Cameras.

3️⃣ Game / Minimax DP ♟️

💡 Signal: two players alternate, both play optimally. Model the score as “best the current player can achieve”, and subtract the opponent’s optimal reply.

Key trick: define solve(state) = best score difference (me − opponent). The opponent’s turn is just -solve(nextState).

Predict the Winner — LC 486 📍

Players pick from either end of nums. Can player 1 tie or win?

// LC 486. Predict the Winner
class Solution {
public:
    vector<vector<int>> dp;
    int solve(vector<int>& nums, int i, int j) {
        if (i == j) return nums[i];                            // only one choice left
        if (dp[i][j] != INT_MIN) return dp[i][j];
        int pickLeft  = nums[i] - solve(nums, i + 1, j);       // opponent plays optimally next
        int pickRight = nums[j] - solve(nums, i, j - 1);
        return dp[i][j] = max(pickLeft, pickRight);
    }
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        dp.assign(n, vector<int>(n, INT_MIN));                 // INT_MIN sentinel: score diff can be negative
        return solve(nums, 0, n - 1) >= 0;                     // >= 0 means player 1 doesn't lose
    }
};
// TC: O(n^2)   SC: O(n^2)

The value - solve(rest) pattern is the whole game

Because whatever the opponent gains is your loss, “my best diff = my pick minus their best diff from what’s left”. Stone Game and Nim-style problems all reduce to this. (Note the INT_MIN sentinel — a score diff of -1 is a real value, so -1 can’t mean “not computed”.)

4️⃣ Probability / Expected-Value DP 🎲

💡 Signal: “probability that …” or “expected number of …”. Same DP, but the combine step is a weighted sum (each branch times its probability), and dp holds doubles.

Knight Probability in Chessboard — LC 688 📍

Probability a knight is still on an n×n board after k random moves.

// LC 688. Knight Probability in Chessboard
class Solution {
public:
    int N;
    vector<vector<vector<double>>> dp;
    double solve(int k, int r, int c) {
        if (r < 0 || c < 0 || r >= N || c >= N) return 0.0;    // stepped off the board
        if (k == 0) return 1.0;                                // survived all k moves
        if (dp[k][r][c] >= 0) return dp[k][r][c];
        int dr[] = {-2,-2,-1,-1,1,1,2,2};
        int dc[] = {-1,1,-2,2,-2,2,-1,1};
        double prob = 0.0;
        for (int d = 0; d < 8; d++)
            prob += solve(k - 1, r + dr[d], c + dc[d]) / 8.0;  // each move equally likely
        return dp[k][r][c] = prob;
    }
    double knightProbability(int n, int k, int row, int column) {
        N = n;
        dp.assign(k + 1, vector<vector<double>>(n, vector<double>(n, -1.0)));
        return solve(k, row, column);
    }
};
// TC: O(k * n^2 * 8)   SC: O(k * n^2)

Combine = expectation

Counting DP sums integers; probability DP sums p(branch) * value(branch). Everything else — state, memo, base case — is unchanged. Use a sentinel like -1.0 since real probabilities are in [0, 1].

5️⃣ Digit DP 🔢

💡 Signal: “count numbers in [L, R] with some digit property” where the range is huge (up to 10^18). You build the number digit by digit, tracking whether you’re still hugging the upper bound.

State: solve(pos, tight, ...problemState). tight = are the digits so far exactly the prefix of N? Only when tight == false are the remaining positions unconstrained → only those states are memoizable.

// Digit DP template — count integers in [0, N] with a digit property
class Solution {
public:
    string num;
    vector<vector<int>> dp;   // dp[pos][state], valid only when tight == false
    int solve(int pos, int state, bool tight) {
        if (pos == (int)num.size()) return 1;         // a full number was formed (adapt per problem)
        if (!tight && dp[pos][state] != -1) return dp[pos][state];
        int limit = tight ? (num[pos] - '0') : 9;     // can't exceed N's digit while tight
        int total = 0;
        for (int d = 0; d <= limit; d++) {
            // if (!allowed(state, d)) continue;       // e.g. no two equal adjacent digits
            int newState = state;                      // update per problem
            total += solve(pos + 1, newState, tight && (d == limit));
        }
        if (!tight) dp[pos][state] = total;            // memoize ONLY the unbounded states
        return total;
    }
    int count(int N) {
        num = to_string(N);
        dp.assign(num.size(), vector<int>(/*num states*/ 10, -1));
        return solve(0, 0, true);
    }
};
// TC: O(digits * states * 10)   SC: O(digits * states)
// For [L, R]: answer = count(R) - count(L - 1).

Why memoize only when !tight

When you’re still tight, the allowed digits depend on N’s exact prefix, so that state isn’t reusable. Once you’ve gone below the bound, the rest is a clean “any digits” subproblem — that’s the part worth caching. Flagship problems: Numbers At Most N Given Digit Set (LC 902), Non-negative Integers without Consecutive Ones (LC 600).

6️⃣ Broken-Profile / Bitmask-on-Grid DP 🧱

💡 Signal: tile / fill a grid (dominoes, 1×2 tiles) where columns ≤ ~14. Process column by column, and the state is a bitmask of which cells in the boundary “profile” are already filled by tiles poking out of the previous column.

Think of it as bitmask DP where the mask describes the jagged frontier between the processed and unprocessed part of the grid. Transitions enumerate how the next column’s cells get covered given the incoming profile.

  • State: dp[col][mask] — ways/cost to fill everything left of col with mask marking cells that stick into col.
  • Flagship: counting domino tilings of an m × n board; Painting a Grid With Three Different Colors (LC 1931) uses the same column-profile idea with a color mask instead of a fill mask.

Niche — recognize, don't memorize

Broken-profile is rare in interviews and heavy to code. Know the shape (column sweep + frontier bitmask, cols ≤ 14) so you can recognize it; reach for a reference implementation when you actually need it.

7️⃣ DP Optimizations ⚡

Sometimes the right DP is obvious but too slow. These turn an O(n²) or O(n·W) DP into something faster by speeding up the transition, not by changing the state.

TechniqueUse when the transition is…Speed-up
Prefix / suffix sumsa sum over a contiguous range of previous statesO(range) → O(1)
Monotonic deque (sliding max)dp[i] = best of dp[i-k..i-1] + cost over a windowO(k) → O(1) amortized
Binary lifting / matrix expoa fixed linear recurrence iterated a huge number of timesO(n) → O(log n)
Knuth’s optimizationinterval DP where the optimal split is monotonicO(n³) → O(n²)
Divide & Conquer optimizationdp[i][j] with monotonic optimal split pointO(kn²) → O(kn log n)
Convex Hull Trick / Li Chaotransition is min/max of linear functions of the stateO(n²) → O(n log n)
Bitsetboolean subset-sum / reachability transitions~64× constant factor
SOS DP (sum over subsets)aggregate over all submasks of each maskO(3^n) → O(2^n · n)

Optimize last

Get the correct DP first (state + recurrence), confirm it’s too slow, then reach for one of these. The classic interview-friendly ones are prefix sums and the monotonic deque (e.g. Jump Game VI, LC 1696); the rest are competitive-programming territory.

🔗 Back to the Core

  • The DP Guide — the 4-rung ladder, the 5 universal patterns, and the nine core interview patterns with full C++.
  • DP Problem Tracker — the curated problem set to drill each pattern.

The one idea that never changes

Bitmask, tree, game, probability, digit — the state gets creative, but you always answer the same four questions: state? choices? combine? base case? Then climb the ladder. Master that and “advanced” is just “a new state”.

Mindmap

Graph View

Backlinks