DP on Grids & Advanced Patterns

The Mental Model

Advanced DP builds on fundamentals with more complex state representations. Grid DP adds spatial dimensions, interval DP considers ranges, and bitmask DP encodes subset information. The core principle remains: define state, find transitions, handle base cases.

Pattern Recognition Signals:

Grid traversal with optimization → Grid DP
“Merge” or “split” segments → Interval DP
Small n (≤ 20) with subset selection → Bitmask DP
“Partition into groups” → Bitmask DP

Pattern 1: Grid DP

State: dp[i][j] = answer for cell (i, j)

Unique Paths

Problem: Count paths from top-left to bottom-right, moving only right or down.

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    
    return dp[m - 1][n - 1];
}

// Space optimized
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    
    return dp[n - 1];
}

Minimum Path Sum

Problem: Find minimum sum path from top-left to bottom-right.

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    dp[0][0] = grid[0][0];
    
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    
    return dp[m - 1][n - 1];
}

Grid with Obstacles

int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (grid[0][0] == 1 || grid[m-1][n-1] == 1) return 0;
    
    vector<vector<long long>> dp(m, vector<long long>(n, 0));
    dp[0][0] = 1;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                if (i > 0) dp[i][j] += dp[i - 1][j];
                if (j > 0) dp[i][j] += dp[i][j - 1];
            }
        }
    }
    
    return dp[m - 1][n - 1];
}

Codeforces Problems:

Problem	Rating	Link
Grid Paths	1500	CSES
Bricks	1300	CF 1404B

Pattern 2: Interval DP

State: dp[i][j] = answer for the interval [i, j] Key Insight: Solve for small intervals first, then larger ones. Often involves choosing a split point k. The Template:

for len = 1 to n:         // Interval length
    for i = 0 to n-len:   // Left endpoint
        j = i + len - 1   // Right endpoint
        for k = i to j:   // Split point
            dp[i][j] = optimize(dp[i][k], dp[k+1][j], cost)

Why this order? When computing dp[i][j], we need dp[i][k] and dp[k+1][j]—both are shorter intervals. By iterating by length, we ensure dependencies are already computed. Visual Example (n=4, computing dp[0][3]):

Length 1: dp[0][0], dp[1][1], dp[2][2], dp[3][3] (base cases)
Length 2: dp[0][1], dp[1][2], dp[2][3]
Length 3: dp[0][2], dp[1][3]
Length 4: dp[0][3] ← needs dp[0][k] and dp[k+1][3] for k=0,1,2
          All those are already computed ✓

Matrix Chain Multiplication

Problem: Minimize cost to multiply chain of matrices. Why order matters: Multiplying matrices A(10×30), B(30×5), C(5×60):

(AB)C: 10×30×5 + 10×5×60 = 1500 + 3000 = 4500 operations
A(BC): 30×5×60 + 10×30×60 = 9000 + 18000 = 27000 operations

State: dp[i][j] = minimum cost to multiply matrices i through j Transition: Try all split points k; cost = dp[i][k] + dp[k+1][j] + dims[i] × dims[k+1] × dims[j+1]

int matrixChainMultiplication(vector<int>& dims) {
    int n = dims.size() - 1;  // n matrices
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // len = length of chain
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            
            // Try all split points
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] 
                         + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    return dp[0][n - 1];
}

Palindrome Partitioning

Problem: Minimum cuts to partition string into palindromes.

int minCut(string& s) {
    int n = s.size();
    
    // isPalin[i][j] = true if s[i..j] is palindrome
    vector<vector<bool>> isPalin(n, vector<bool>(n, false));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i <= 2 || isPalin[i + 1][j - 1])) {
                isPalin[i][j] = true;
            }
        }
    }
    
    // dp[i] = min cuts for s[0..i]
    vector<int> dp(n, 0);
    for (int i = 0; i < n; i++) {
        if (isPalin[0][i]) {
            dp[i] = 0;
        } else {
            dp[i] = i;  // Maximum cuts
            for (int j = 1; j <= i; j++) {
                if (isPalin[j][i]) {
                    dp[i] = min(dp[i], dp[j - 1] + 1);
                }
            }
        }
    }
    
    return dp[n - 1];
}

Burst Balloons

Problem: Burst balloons to maximize coins. Bursting balloon i gives nums[left] * nums[i] * nums[right] coins. Key Insight: Think backwards—which balloon do we burst last in a range?

int maxCoins(vector<int>& nums) {
    int n = nums.size();
    
    // Add 1s at boundaries
    vector<int> arr(n + 2);
    arr[0] = arr[n + 1] = 1;
    for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
    n += 2;
    
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int len = 2; len < n; len++) {
        for (int left = 0; left < n - len; left++) {
            int right = left + len;
            
            for (int k = left + 1; k < right; k++) {
                // k is the LAST balloon burst in (left, right)
                dp[left][right] = max(dp[left][right],
                    dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]);
            }
        }
    }
    
    return dp[0][n - 1];
}

Pattern 3: Bitmask DP

State: dp[mask] where mask is a binary representation of a subset. When to Use: n ≤ 20 (since 2^20 ≈ 10^6)

Traveling Salesman Problem (TSP)

Problem: Visit all cities exactly once and return to start with minimum cost.

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    int INF = 1e9;
    
    // dp[mask][i] = min cost to reach city i, having visited cities in mask
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;  // Start at city 0
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;  // u not in mask
            if (dp[mask][u] == INF) continue;
            
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;  // v already visited
                
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // Return to city 0
    int allVisited = (1 << n) - 1;
    int ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[allVisited][i] + dist[i][0]);
    }
    
    return ans;
}

Counting Subsets

Problem: Partition n elements into groups, each group following rules.

// Example: Count ways to partition n people into teams of size k
int countPartitions(int n, int k) {
    // dp[mask] = ways to partition people in mask into teams
    vector<long long> dp(1 << n, 0);
    dp[0] = 1;
    
    // Precompute valid teams (subsets of size k)
    vector<int> validTeams;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount(mask) == k) {
            validTeams.push_back(mask);
        }
    }
    
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == 0) continue;
        
        // Find first unassigned person (to avoid counting same partition twice)
        int first = -1;
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                first = i;
                break;
            }
        }
        if (first == -1) continue;
        
        for (int team : validTeams) {
            // Team must include 'first' and not overlap with mask
            if (!(team & (1 << first))) continue;
            if (team & mask) continue;
            
            dp[mask | team] += dp[mask];
        }
    }
    
    return dp[(1 << n) - 1];
}

Bitmask Tricks

// Iterate over all subsets of mask
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // sub is a subset of mask
}

// Count set bits
int count = __builtin_popcount(mask);

// Check if bit i is set
bool isSet = (mask >> i) & 1;

// Set bit i
mask |= (1 << i);

// Clear bit i  
mask &= ~(1 << i);

// Toggle bit i
mask ^= (1 << i);

// Get lowest set bit
int lowest = mask & (-mask);

// Clear lowest set bit
mask &= (mask - 1);

Codeforces Problems:

Problem	Rating	Link
Hamiltonian Flights	1600	CSES
Elevator Rides	1700	CSES
SOS DP	1900	CF 165E

Pattern 4: DP with Optimization

Prefix Sum Optimization

When transition involves sum over range, precompute prefix sums.

Monotonic Queue Optimization

When dp[i] = min/max(dp[j] + cost(j, i)) for j in sliding window.

// Example: Jump Game with max k jumps, minimize sum of heights
int minCost(vector<int>& heights, int k) {
    int n = heights.size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;
    
    deque<int> dq;  // Monotonic deque of indices
    dq.push_back(0);
    
    for (int i = 1; i < n; i++) {
        // Remove out-of-range elements
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }
        
        dp[i] = dp[dq.front()] + abs(heights[i] - heights[dq.front()]);
        
        // Maintain monotonicity
        while (!dq.empty() && dp[dq.back()] >= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    
    return dp[n - 1];
}

Common Mistakes

Mistake 1: Wrong Interval DP Order Always iterate by length, not by starting index:

// CORRECT
for (int len = 1; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        // Process [i, j]
    }
}

Mistake 2: Bitmask Overflow

// WRONG for n > 30
int mask = 1 << n;

// CORRECT for n up to 62
long long mask = 1LL << n;

Mistake 3: Grid DP Boundary Always check boundaries before accessing dp[i-1][j] or dp[i][j-1].

Practice Problems

Grid DP (1300-1500)

Problem	Pattern	Link
Grid Paths	Basic grid	CSES
Longest Path in Grid	Max path	AtCoder DP H
Triangle	Grid variant	CF 1201C

Interval DP (1500-1700)

Problem	Pattern	Link
Removal Game	Two-player	CSES
Palindrome Removal	Interval	LeetCode

Bitmask DP (1600-1900)

Problem	Pattern	Link
Matching	Assignment	CSES
Elevator Rides	Optimization	CSES
Hamiltonian	TSP	CSES

Key Takeaways

Grid = 2D State

dp[i][j] represents answer at position (i, j).

Interval = Small to Large

Solve small intervals first, combine for larger.

Bitmask = Subset

When n ≤ 20, encode subset selection in bits.

Think Backwards

Sometimes easier to think “what happens last?”

Next Up

Chapter 13: Graph Fundamentals

Enter the world of graphs—the most versatile data structure in competitive programming.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

DP on Grids & Advanced Patterns

DP on Grids & Advanced Patterns

The Mental Model

Pattern 1: Grid DP

Unique Paths

Minimum Path Sum

Grid with Obstacles

Pattern 2: Interval DP

Matrix Chain Multiplication

Palindrome Partitioning

Burst Balloons

Pattern 3: Bitmask DP

Traveling Salesman Problem (TSP)

Counting Subsets

Bitmask Tricks

Pattern 4: DP with Optimization

Prefix Sum Optimization

Monotonic Queue Optimization

Common Mistakes

Practice Problems

Grid DP (1300-1500)

Interval DP (1500-1700)

Bitmask DP (1600-1900)

Key Takeaways

Grid = 2D State

Interval = Small to Large

Bitmask = Subset

Think Backwards

Next Up

Chapter 13: Graph Fundamentals

​DP on Grids & Advanced Patterns

​The Mental Model

​Pattern 1: Grid DP

​Unique Paths

​Minimum Path Sum

​Grid with Obstacles

​Pattern 2: Interval DP

​Matrix Chain Multiplication

​Palindrome Partitioning

​Burst Balloons

​Pattern 3: Bitmask DP

​Traveling Salesman Problem (TSP)

​Counting Subsets

​Bitmask Tricks

​Pattern 4: DP with Optimization

​Prefix Sum Optimization

​Monotonic Queue Optimization

​Common Mistakes

​Practice Problems

​Grid DP (1300-1500)

​Interval DP (1500-1700)

​Bitmask DP (1600-1900)

​Key Takeaways

Grid = 2D State

Interval = Small to Large

Bitmask = Subset

Think Backwards

​Next Up

Chapter 13: Graph Fundamentals

DP on Grids & Advanced Patterns

The Mental Model

Pattern 1: Grid DP

Unique Paths

Minimum Path Sum

Grid with Obstacles

Pattern 2: Interval DP

Matrix Chain Multiplication

Palindrome Partitioning

Burst Balloons

Pattern 3: Bitmask DP

Traveling Salesman Problem (TSP)

Counting Subsets

Bitmask Tricks

Pattern 4: DP with Optimization

Prefix Sum Optimization

Monotonic Queue Optimization

Common Mistakes

Practice Problems

Grid DP (1300-1500)

Interval DP (1500-1700)

Bitmask DP (1600-1900)

Key Takeaways

Next Up