Two-Dimensional Dynamic Programming
Two-dimensional DP stores one answer for each pair of state coordinates, making dependencies and evaluation order explicit in a table.
When a state needs two coordinates
A DP table is two-dimensional when a subproblem is determined by two independent coordinates: prefixes of two strings, grid row and column, interval endpoints, or items and capacity. The dimensions describe state, not necessarily the physical shape of the input.
Write a sentence such as dp[i][j] is the best answer using the first i characters and first j characters. Without that invariant, a recurrence may combine values that answer different questions and still appear numerically plausible.
- Dimensions encode the complete subproblem
- Coordinates may be prefixes or resources
- State meaning precedes code
Transitions and dependency order
A transition lists every legal final decision and reduces it to already solved states. Grid paths use top and left; edit distance also uses diagonal; knapsack uses a previous item row. Draw dependency arrows before choosing loop order.
Bottom-up loops must respect those arrows. If a cell reads the current row to its right, left-to-right order is wrong. Top-down memoization avoids manual order but consumes recursion depth and still needs a key containing both coordinates.
- Transitions enumerate last choices
- Arrows determine loop order
- Memo keys need both coordinates
Terms, operations, and practical uses
State design
- Table coordinateTable coordinate is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Base stateBase state is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- TransitionTransition is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Dependencies
- Fill orderFill order is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Top-down memoizationTop-down memoization is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Space compressionSpace compression is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Examples
- Grid pathGrid path is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Edit distanceEdit distance is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- ReconstructionReconstruction is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Fill a two-dimensional minimum-path table
g=[[1,3,1],[1,5,1],[4,2,1]];r=len(g);c=len(g[0]);dp=[[0]*c for _ in range(r)]
for i in range(r):
for j in range(c):
if i==0 and j==0:dp[i][j]=g[i][j]
else:dp[i][j]=g[i][j]+min(dp[i-1][j] if i else 10**9,dp[i][j-1] if j else 10**9)
print("Minimum path sum:",dp[-1][-1])#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> g={{1,3,1},{1,5,1},{4,2,1}},dp(3,vector<int>(3));
for(int i=0;i<3;i++) for(int j=0;j<3;j++) dp[i][j]=g[i][j]+((i||j)?min(i?dp[i-1][j]:1000000000,j?dp[i][j-1]:1000000000):0);
cout << "Minimum path sum: " << dp[2][2] << '\n';
}class Main {
public static void main(String[] args) {
int[][] g={{1,3,1},{1,5,1},{4,2,1}},dp=new int[3][3];
for(int i=0;i<3;i++) for(int j=0;j<3;j++) dp[i][j]=g[i][j]+((i>0||j>0)?Math.min(i>0?dp[i-1][j]:1_000_000_000,j>0?dp[i][j-1]:1_000_000_000):0);
System.out.println("Minimum path sum: "+dp[2][2]);
}
}Step through it
Running on grid [[1,3,1],[1,5,1],[4,2,1]]
Boundaries are part of the recurrence
Extra row zero and column zero often represent empty prefixes and remove conditionals from the inner loop. Their values are problem-specific: zero for LCS length, insertion/deletion counts for edit distance, or infinity for unreachable optimization states.
Do not initialize an entire table to zero when zero is a valid answer but not a reachable state. A sentinel must remain distinguishable until a transition proves reachability; otherwise impossible paths can win a minimum.
- Model empty-prefix states
- Choose identity or infinity deliberately
- Reachability and value are separate facts
Space compression and reconstruction
If row i depends only on row i−1, keep two rows for O(columns) memory. If a transition also reads the current row, update in the direction that preserves needed cells. One-row compression changes code order and deserves its own proof.
Compression often discards the choices needed to reconstruct an alignment or path. Keep the full table, store parent decisions, or recompute selectively when the actual solution—not only its value—is required.
- Two rows often suffice
- Update direction protects old values
- Reconstruction may require extra state
Complexity and verification
An R×C table with O(1) work per cell costs O(RC) time and space before compression. Ragged grids, forbidden cells, weighted transitions, and multiple valid optima do not change the counting method but do change initialization and parents.
Test empty dimensions, one row, one column, unreachable targets, ties, and values near overflow. Hand-compute a tiny table and compare every cell, not only the final corner; a wrong intermediate state can coincidentally produce the expected final answer.
- Count states times transitions
- Test every boundary dimension
- Inspect intermediate cells
A state-design review
Before implementation, list the coordinates, allowed ranges, semantic meaning, base states, and every predecessor. For edit distance, for example, dp[i][j] covers two prefixes; deletion, insertion, and replacement point to three distinct neighbors. This written contract makes the table independently reviewable instead of tying its meaning to loop variables.
When the table is large, choose the smaller input for the compressed dimension where symmetry permits. Measure memory as cells times bytes, not big-O alone. If transitions scan another dimension, complexity is states times transition count rather than merely O(RC).
Finally, distinguish tabulation coordinates from input indexes: an extra boundary row shifts character i to table row i+1. Label this shift in the tracer and keep one interval convention throughout reconstruction. Cross-check the complete table against a top-down implementation on randomized small inputs.
A reliable review technique is to compute a tiny table by hand and annotate which predecessor justified each cell. This separates a correct numeric answer from a correct recurrence: two bugs can occasionally cancel on one example. For rectangular inputs, test one-row and one-column shapes because they expose boundary initialization errors hidden by square examples. If obstacles or impossible states exist, use an explicit infinity sentinel and guard arithmetic on it. Reconstruction should follow stored choices until the base state, then reverse the collected operations or coordinates. The table value proves the optimum; the parent choices supply the witness that achieves it.
- Document coordinates and ranges
- Count transition work per cell
- Choose compression from dependencies