Pattern

2-D DP

Tackle grid and matrix problems with two-dimensional DP.

8 Problems

0 Easy

7 Medium

1 Hard

How 2-D DP Works

2D Dynamic Programming extends 1D DP to problems with two varying parameters, using a 2D table where dp[i][j] represents the solution for a subproblem defined by indices i and j. Common patterns include grid traversal (paths from top-left to bottom-right), string matching (edit distance, LCS), and knapsack problems (items vs capacity). Each cell depends on its neighbors (usually left, top, or diagonal), and you fill the table row by row.

When to Use 2-D DP

Pattern Recognition

Look for these trigger words in problem statements:

unique paths 2d-dp longest common subsequence best time to buy and sell stock with cooldown coin change ii target sum interleaving string edit distance burst balloons

Common Mistakes

Wrong table dimensions — often need (m+1) x (n+1) to handle empty string/array base cases
Filling the table in the wrong order (dependencies must already be computed)
Not initializing the first row and column correctly
Using O(mn) space when O(n) suffices by only keeping the current and previous rows

When NOT to Use 2-D DP

When the problem only has one varying parameter (1D DP is sufficient)
When the grid/table is too large (consider memoization with pruning)
When the problem requires tracking more state than two indices can capture

Practice Problems

Easy (0) Medium (7) Hard (1)

Unique Paths medium Longest Common Subsequence medium Best Time to Buy and Sell Stock with Cooldown medium Coin Change II medium Target Sum medium Interleaving String medium Edit Distance medium Burst Balloons hard

Master 2-D DP

Build pattern recognition with interactive MCQs. Understand why to use 2-D DP, not just how.

Download LeetEye Free