> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# DP on Grids & Advanced Patterns

> Master 2D DP, interval DP, and bitmask DP for ICPC-level problems

# 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.

<Note>
  **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
</Note>

***

## 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.

```cpp theme={null}
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.

```cpp theme={null}
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

```cpp theme={null}
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](https://cses.fi/problemset/task/1638)                 |
| Bricks     | 1300   | [CF 1404B](https://codeforces.com/problemset/problem/1404/B) |

***

## 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]

```cpp theme={null}
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.

```cpp theme={null}
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?

```cpp theme={null}
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.

```cpp theme={null}
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.

```cpp theme={null}
// 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

```cpp theme={null}
// 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](https://cses.fi/problemset/task/1690)               |
| Elevator Rides      | 1700   | [CSES](https://cses.fi/problemset/task/1653)               |
| SOS DP              | 1900   | [CF 165E](https://codeforces.com/problemset/problem/165/E) |

***

## 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.

```cpp theme={null}
// 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

<Warning>
  **Mistake 1: Wrong Interval DP Order**
  Always iterate by length, not by starting index:

  ```cpp theme={null}
  // 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]
      }
  }
  ```
</Warning>

<Warning>
  **Mistake 2: Bitmask Overflow**

  ```cpp theme={null}
  // WRONG for n > 30
  int mask = 1 << n;

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

<Warning>
  **Mistake 3: Grid DP Boundary**
  Always check boundaries before accessing dp\[i-1]\[j] or dp\[i]\[j-1].
</Warning>

***

## Practice Problems

### Grid DP (1300-1500)

| Problem              | Pattern      | Link                                                         |
| -------------------- | ------------ | ------------------------------------------------------------ |
| Grid Paths           | Basic grid   | [CSES](https://cses.fi/problemset/task/1638)                 |
| Longest Path in Grid | Max path     | [AtCoder DP H](https://atcoder.jp/contests/dp/tasks/dp_h)    |
| Triangle             | Grid variant | [CF 1201C](https://codeforces.com/problemset/problem/1201/C) |

### Interval DP (1500-1700)

| Problem            | Pattern    | Link                                                                    |
| ------------------ | ---------- | ----------------------------------------------------------------------- |
| Removal Game       | Two-player | [CSES](https://cses.fi/problemset/task/1097)                            |
| Palindrome Removal | Interval   | [LeetCode](https://leetcode.com/problems/minimum-cost-to-merge-stones/) |

### Bitmask DP (1600-1900)

| Problem        | Pattern      | Link                                         |
| -------------- | ------------ | -------------------------------------------- |
| Matching       | Assignment   | [CSES](https://cses.fi/problemset/task/1690) |
| Elevator Rides | Optimization | [CSES](https://cses.fi/problemset/task/1653) |
| Hamiltonian    | TSP          | [CSES](https://cses.fi/problemset/task/1690) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="Grid = 2D State" icon="table-cells">
    dp\[i]\[j] represents answer at position (i, j).
  </Card>

  <Card title="Interval = Small to Large" icon="arrows-left-right">
    Solve small intervals first, combine for larger.
  </Card>

  <Card title="Bitmask = Subset" icon="binary">
    When n ≤ 20, encode subset selection in bits.
  </Card>

  <Card title="Think Backwards" icon="rotate-left">
    Sometimes easier to think "what happens last?"
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 13: Graph Fundamentals" icon="arrow-right" href="/courses/competitive-programming/13-graph-fundamentals">
  Enter the world of graphs—the most versatile data structure in competitive programming.
</Card>