DP on Grids & Intervals — Algorithms Course

What you'll learn

Two more DP shapes complete your toolkit. Grid DP walks a 2-D board cell by cell; interval DP builds answers for larger and larger ranges by choosing a split point. Together they cover a huge swath of interview and contest problems.

By the end you'll be able to:

Solve path-counting and min-cost problems on a grid
Set up an interval DP over ranges
Recognize matrix-chain and palindrome-partition problems

DP on grids

On a grid where you move only right or down, the number of paths to a cell is the paths from above plus the paths from the left — dp[r][c] = dp[r-1][c] + dp[r][c-1], with the edges seeded to 1. Watch the counts accumulate toward the far corner:

Counting grid paths (3 × 4)

Unique grid paths

r\c

dp[r][c] = dp[r-1][c] + dp[r][c-1]

computing depends on answer

1/14Count paths from the top-left to each cell, moving only right or down.

Each interior cell sums the cell above and the cell to its left.

In code

Language

unique_paths.py

def unique_paths(rows, cols):
    dp = [[1] * cols for _ in range(rows)]   # edges have 1 path
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]   # above + left
    return dp[rows - 1][cols - 1]

Tip

Variants swap the transition: minimum path sum uses grid[r][c] + min(up, left); obstacles set blocked cells to 0. The grid shape stays the same — only the recurrence changes.

Interval DP

In interval DP the state is a range dp[i][j], and the transition tries every split point k inside it: dp[i][j] = best over k of (dp[i][k] + dp[k+1][j] + cost). You fill by increasing interval length, so both halves are already solved. It's O(n³): O(n²) intervals times O(n) split points.

Note

The order of filling matters: iterate over interval length from small to large (not left-to-right), so that dp[i][k] and dp[k+1][j] are ready when you need them.

Matrix-chain & palindromes

Matrix-chain multiplication: given matrix dimensions, parenthesize the product to minimize scalar multiplications. dp[i][j] is the cheapest way to multiply matrices i..j; the split k is where you place the outer multiplication.
Palindrome partitioning: the fewest cuts to split a string into palindromes — an interval DP where a range costs 0 if it's already a palindrome, else 1 + the best split.

Recap & quick check

Key takeaways

Grid DP: dp[r][c] combines the cell above and the cell to the left.
Min path sum and obstacle grids just change the transition, not the shape.
Interval DP: dp[i][j] tries every split k inside the range.
Fill interval DP by increasing length so both halves are ready — O(n³).
Matrix-chain and palindrome partitioning are classic interval DPs.

Quick check

1. For counting right/down grid paths, dp[r][c] equals:

2. What is the state in interval DP?

3. In what order do you fill an interval DP?

4. Matrix-chain multiplication decides:

Finally, DP escapes the grid — onto trees and over subsets of items. Next up: Module 20 — Advanced DP: Trees & Bitmask.