DSA AnimatorDSA animations
Unique Paths LC #62 Medium 2D DP
Problem

A robot on an m × n grid starts at top-left and moves to bottom-right. It can only move right or down. Return the number of unique paths.

Example 1
Input: m = 3, n = 7
Output: 28
Example 2
Input: m = 3, n = 3
Output: 6
Constraints: 1 ≤ m, n ≤ 100
Try Examples
Custom:
Approach
2D DP — dp[r][c] = paths to reach (r,c)
Recurrence: dp[r][c] = top + left. Base: dp[0][0]=1. Robot moves right or down only.
Grid Fill
Load an example to begin.
Variables
cell (r,c)
—
top
—
left
—
paths
—
Step Logic
Press ▶ Play or Next Step to begin.
🎯
Ready
0 / 0
Select an example and press Play.
Algorithm
1
dp[r][c] = paths to reach (r,c). Only right or down.
2
dp[r][c] = top + left (paths from above + from left)
3
Base: dp[0][0]=1. First row & col = 1.
4
Answer = dp[m-1][n-1]
Time
O(m×n)
Space
O(n)
Why This Works

To reach (r,c) you must come from (r-1,c) or (r,c-1). So paths[r][c] = paths from above + paths from left. First row and column are 1 (one straight path). Fill top-to-bottom, left-to-right so dependencies are ready.

How to solve Unique Paths

LeetCode 62 · Easy · Dynamic Programming · Pattern: 2D Grid DP

Why the obvious approach is slow

Exploring every path recursively visits the same cells many times. The number of paths explodes as the grid grows.

The key idea

The robot can only enter a cell from above or from the left. So paths to a cell equals paths to the cell above plus paths to the cell on the left. Every cell in the first row or first column has exactly one path, a straight line. Fill the grid row by row, and the bottom right cell holds the answer.

Remember

Paths into a cell equal the sum of paths into the cells that lead to it. One row of memory is enough.

Run the animation above on your own input, or watch the 1:34 video explanation of Unique Paths with a dry run and Java code.

More Dynamic Programming problems