2D Dynamic Programming

Two-dimensional DP appears when one coordinate is not enough to describe the subproblem. Common dimensions are (row, col), (i, j) across two strings, (left, right) for intervals, or (day, state) for trading and cooldown constraints.

Mental Model

• Grid DP: paths and obstacles use top/left transitions.
• Two-string DP: compare prefixes text1[0..i) and text2[0..j).
• Interval DP: solve smaller ranges before larger ranges.
• State-machine DP: each day/index has several modes such as holding, sold, or cooldown.

Diagram

Problem List

Start with 062. Unique Paths, 1143. Longest Common Subsequence, 072. Edit Distance, 518. Coin Change 2, and 312. Burst Balloons.