Week 14: Dynamic Programming II: Grids, Trees & Interval DP

1. DP on Grids with Obstacles

Grid DP extends the "define dp[i] in terms of earlier states" idea to two dimensions: dp[i][j] depends on the cell above it and the cell to its left. Obstacles are handled by forcing any blocked cell's count to zero, which then correctly propagates "unreachable" forward through the rest of the grid.

grid_dp.cpp

#include <vector>
using namespace std;

// Count paths from top-left to bottom-right, moving only right/down,
// where grid[i][j] == 1 marks an obstacle -- O(rows * cols) time and space
int uniquePathsWithObstacles(const vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<long long>> dp(rows, vector<long long>(cols, 0));

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0;   // obstacle: unreachable
                continue;
            }
            if (i == 0 && j == 0) {
                dp[i][j] = 1;   // starting cell
            } else {
                long long fromTop = (i > 0) ? dp[i - 1][j] : 0;
                long long fromLeft = (j > 0) ? dp[i][j - 1] : 0;
                dp[i][j] = fromTop + fromLeft;
            }
        }
    }
    return (int)dp[rows - 1][cols - 1];
}

Fill order matters just as much as the recurrence

Processing cells in row-major order guarantees dp[i-1][j] and dp[i][j-1] are always already computed before you need them — the same "process dependencies before dependents" discipline you used for topological order in Week 12, just applied along two axes instead of one.

2. DP on Trees

DP on trees runs a post-order recursion where each call returns not just one number, but a small bundle of answers under different local constraints — one per child state the parent might care about. The classic example is "House Robber III": robbing houses arranged in a binary tree, where you can't rob two directly-connected nodes.

tree_dp.cpp

#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Returns {best sum if we ROB this node, best sum if we DON'T rob this node}
pair<int,int> robTreeHelper(TreeNode* node) {
    if (!node) return {0, 0};

    auto [leftRob, leftSkip] = robTreeHelper(node->left);
    auto [rightRob, rightSkip] = robTreeHelper(node->right);

    int rob = node->val + leftSkip + rightSkip;                     // take node -> children must be skipped
    int skip = max(leftRob, leftSkip) + max(rightRob, rightSkip);   // free choice per child

    return {rob, skip};
}

// O(n) time -- one post-order pass, O(h) space for the call stack
int robTree(TreeNode* root) {
    auto [rob, skip] = robTreeHelper(root);
    return max(rob, skip);
}

Same shape as diameter-of-tree

Returning a small struct or pair of "answer under each local constraint" from every recursive call, computed post-order, is the same pattern you used for the diameter-of-a-tree problem in Week 10 — DP on trees is almost always that pattern with a different pair of values being tracked.

3. Interval DP: Matrix Chain Multiplication

Every DP you've written so far indexes state by a prefix — dp[i] or dp[i][j] meaning "the best answer using the first i elements." Interval DP indexes state by a range instead: dp[i][j] means "the best answer for the subarray from i to j inclusive," and the recurrence tries every way to split that range at some point k and combines the two halves. Matrix chain multiplication is the canonical example: given a chain of matrices, find the parenthesization that minimizes the total number of scalar multiplications, since multiplication is associative but the cost of each order differs enormously.

matrix_chain.cpp

#include <vector>
#include <climits>
using namespace std;

// dims[i-1] x dims[i] is the shape of matrix i (1-indexed), for i in [1, n]
// dp[i][j] = min scalar multiplications to compute the product of matrices i..j
// O(n^3) time, O(n^2) space
int matrixChainOrder(vector<int>& dims) {
    int n = dims.size() - 1;              // number of matrices
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // len is the interval length -- intervals of length 1 (single matrices) cost 0
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {        // try every split point
                int cost = dp[i][k] + dp[k + 1][j]
                         + dims[i - 1] * dims[k] * dims[j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[1][n];
}

The outer loop over len is what makes this DP correct: to fill dp[i][j] you need every smaller sub-interval already computed, so processing intervals in increasing order of length guarantees every dp[i][k] and dp[k+1][j] the inner loop reads is ready before it's read — the same "dependencies before dependents" discipline as grid DP's row-major fill, just organized by interval size instead of row.

Recognize the shape, not the story

Any problem asking "what's the optimal way to combine/merge/multiply a sequence, where order changes the cost" is almost always interval DP wearing a different costume — burst balloons, optimal BST construction, and polygon triangulation all reduce to the exact same dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + mergeCost(i, k, j) recurrence.

4. Palindrome Partitioning: Minimum Cuts

Given a string, partition it into the fewest possible substrings such that every substring is a palindrome, and return the minimum number of cuts needed. This combines interval thinking (precomputing which [i, j] ranges are palindromes) with prefix DP (the fewest cuts to partition everything up to index i).

palindrome_partition.cpp

#include <vector>
#include <string>
using namespace std;

// Minimum cuts to partition s into palindromic substrings -- O(n^2) time and space
int minCut(const string& s) {
    int n = s.size();

    // isPalin[i][j]: is s[i..j] a palindrome? Built from shorter intervals outward.
    vector<vector<bool>> isPalin(n, vector<bool>(n, false));
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] != s[j]) continue;
            isPalin[i][j] = (len <= 2) || isPalin[i + 1][j - 1];
        }
    }

    // cuts[i] = min cuts needed for the prefix s[0..i]
    vector<int> cuts(n, 0);
    for (int i = 0; i < n; i++) {
        if (isPalin[0][i]) { cuts[i] = 0; continue; }   // whole prefix is already a palindrome
        cuts[i] = i;   // worst case: cut before every character
        for (int j = 1; j <= i; j++) {
            if (isPalin[j][i] && cuts[j - 1] + 1 < cuts[i]) {
                cuts[i] = cuts[j - 1] + 1;
            }
        }
    }
    return cuts[n - 1];
}

Precomputing isPalin is itself interval DP — s[i..j] is a palindrome exactly when its endpoints match and the interval one shorter on each side, s[i+1..j-1], is also a palindrome, filled in order of increasing length just like matrix chain. That precomputation turns what would be an O(n) palindrome check inside the main loop into an O(1) lookup, which is what keeps the overall algorithm at O(n²) instead of O(n³).

Precompute the interval table before the prefix DP

Whenever a prefix or subsequence DP's transition needs to ask "is this range valid/a palindrome/sorted?" repeatedly, build an O(n²) lookup table for that question first with its own interval DP, exactly like isPalin here — recomputing the check inline is the single most common way this pattern accidentally becomes O(n³) or worse.

5. Hands-on Exercise

Hands-on

Build a Two-Dimensional DP Toolkit

Implement all four state shapes from this week and confirm each on a hand-worked example.

Requirements:

Implement uniquePathsWithObstacles and test it on a grid with a fully blocked row (expect 0 paths).
Implement robTree on a sample binary tree and confirm it matches a brute-force recursive solution that doesn't use the post-order pair trick.
Implement matrixChainOrder for the dims array {40, 20, 30, 10, 30} and confirm it returns 26000.
Implement minCut for "aab" and confirm it returns 1 (cut into "aa" and "b"), and for "a" confirm it returns 0.
Extend matrixChainOrder to also return the actual optimal parenthesization as a string, by tracking the best split point k for each dp[i][j] in a separate table and reconstructing recursively.
Write a one-line comment above each function stating its state definition (what dp[i][j] or the returned pair means) and its time complexity.

Hint

For the reconstruction in requirement 5, add a parallel vector<vector<int>> split table sized like dp; every time you update dp[i][j] to a new best cost inside the k loop, also record split[i][j] = k. A small recursive helper that reads split[i][j] can then rebuild the full parenthesization from dp[1][n] down.

6. Knowledge Check

Four quick questions. Expand each to check your answer.

Why does the DP-on-trees pattern for House Robber III return a pair (rob this node, skip this node) from each recursive call instead of a single value?

A parent node's own decision depends on whether each child was robbed or skipped — if the parent is robbed, its children must be in their "skip" state, but if the parent is skipped, each child is free to be in whichever state is larger. Returning only one number per child would throw away exactly the information the parent needs to make that decision correctly.

In matrix chain multiplication, why must the outer loop iterate by increasing interval length rather than by increasing `i`?

Computing dp[i][j] requires dp[i][k] and dp[k+1][j] for every split point k — both of which are strictly shorter intervals than [i, j]. Iterating by increasing length guarantees every shorter interval a longer one depends on has already been filled in, while iterating by increasing i alone gives no such guarantee, since dp[i][j] for a large j could still depend on an unfilled dp[k+1][j] with a larger starting index.

In the palindrome partitioning solution, what would go wrong (asymptotically) if `isPalin` were not precomputed and each palindrome check were done inline instead?

The main loop already does O(n²) work — an outer loop over i and an inner loop over j. An inline palindrome check on s[j..i] costs O(n) in the worst case, which multiplied across that O(n²) loop pushes the total to O(n³). Precomputing isPalin first, itself an O(n²) pass, turns every check inside the main loop into an O(1) lookup and keeps the overall algorithm at O(n²).

What is the general signal that a problem calls for interval DP (state over a range) rather than prefix DP (state over a prefix)?

Interval DP fits when the answer for a segment depends on how that segment itself gets split or combined internally — merging matrices, cutting a string, triangulating a polygon — so the recurrence needs to try every internal split point k and combine both halves. Prefix DP fits when each new element is decided once, in order, based only on what came before it, with no need to reconsider how an earlier segment was internally structured.