DP / Core2D DPMedium

2D DP — Unique Paths in a Grid

Count paths from top-left to bottom-right moving only right or down. dp[i][j] = dp[i-1][j] + dp[i][j-1].

LC
Practice on LeetCode 62: Unique Paths
Open Problem

From 1D to 2D

A 2D DP uses a grid/table where each cell depends on its neighbors. In Unique Paths, cell (i,j) can be reached from above (i-1,j) or from the left (i,j-1). First row and column are all 1s (only one way to reach them).

Recurrence

dp[0][j] = 1 // first row
dp[i][0] = 1 // first column
dp[i][j] = dp[i-1][j] + dp[i][j-1]
// from above + from left
Interactive Visualization
Base Case
Source Cells
Computing
Answer
Step 0 of 0
Cell
—
From Above + Left
—
Value
—
Answer
—
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — Unique Paths
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));

    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];

    return dp[m-1][n-1];
}
Complexity
Time
O(M × N)

Fill every cell once.

Space
O(M × N)

Can optimize to O(N) with row-by-row.

📝 Notes

▼