← DSA Atlas
Dedicated problem page · #62

Unique Paths

MediumTwo-Dimensional Dynamic ProgrammingGrid path-counting DP2D dynamic programming
Solve on LeetCode ↗
62
MediumTwo-Dimensional Dynamic Programming2D dynamic programmingGrid path-counting DP

Unique Paths

A robot starts at the top-left corner of an m x n grid and wants to reach the bottom-right corner. It can only move either one step right or one step down at any point. Return the number of distinct paths it can take.

Open official problem prompt ↗
In plain English

We want to count, not find, every right/down route across the grid.

Picture it like this

Like Pascal's triangle laid flat: the ways to reach a spot are the ways to reach the two spots feeding into it, added together.

Example
Input
m = 3, n = 7
Output
28
Why
There are 28 distinct right/down routes from the top-left to the bottom-right of a 3x7 grid.
Constraints
1 <= m, n <= 100The answer is guaranteed to be at most 2 * 10^9.
Pattern lesson

See the pattern, then code

Grid path-counting DP
Recognition clue

Counting distinct monotone routes through a grid where moves are only right or down is the canonical grid-DP (or combinatorics) problem.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Every cell is reached only from directly above or directly to its left, so the number of ways to reach it is the sum of those two neighbors' counts.

New words, made simpleKnow these before the algorithm
Monotone path
A route that only ever moves right or down, never back.
Additive recurrence
A cell's value is the sum of the cells that can reach it.
Base row/column
The top edge and left edge each have exactly one path.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Enumerate all paths

Exponential; recomputes the same cells constantly.

Recursively try right and down until reaching the corner, counting arrivals.

Time O(2^(m+n))Space O(m+n)
Best choice2D grid DP

Linear in the grid size and simple; the recommended approach (a closed-form binomial C(m+n-2, m-1) also works).

Fill counts row by row using dp[i][j] = dp[i-1][j] + dp[i][j-1].

Time O(m*n)Space O(m*n)
The rule we keep true

Invariant

dp[i][j] equals the number of distinct right/down paths from (0,0) to cell (i,j).

Why this is correct

Reasoning

The last move into any interior cell is either from above or from the left, and these two sets of paths are disjoint and cover all paths; summing their counts therefore counts every path to that cell exactly once. The edges have one path each, anchoring the induction.

The algorithm in three movesSay these aloud before coding
1Initialize the first row and first column to 1 (a single straight path)

row0 = 1 1 1 1 1 1 1

2For every interior cell set dp[i][j] = dp[i-1][j] + dp[i][j-1]

row1 = 1 2 3 4 5 6 7

3Return dp[m-1][n-1]

row2[6] = 28

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
11
12
13
24
35
46
1 · Readfirst row and column
2 · AskHow many ways along an edge?
3 · Update stateall 1s on row 0 and column 0
4 · Resultedges initialized
Key takeaway

The first two rows of the counts; each interior cell sums the cell above and the cell to its left.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Initialize to ones

    Filling the whole grid with 1 pre-seeds the first row and column, which each have a single path.

  2. 2
    Lines 4-6Interior recurrence

    Every non-edge cell adds the counts from above and from the left.

  3. 3
    Lines 7Return

    The bottom-right cell holds the total path count.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A 1 x n or m x 1 grid has exactly 1 path
  • m = n = 1 returns 1 (already at the destination)
  • Large 100 x 100 grids stay within the stated 2*10^9 bound
!

Common beginner mistakes

  • Swapping the roles of m (rows) and n (columns) when allocating
  • Not initializing the first row/column, leaving zeros
  • Reaching for recursion without memoization and timing out conceptually
Check your understanding

Why can the first row and first column both be initialized to 1?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#72Edit DistanceSequence-alignment grid DP#10Regular Expression MatchingPattern-matching grid DP with star lookback#44Wildcard MatchingGlob-matching grid DP#63Unique Paths IIGrid path-counting DP with obstacles#64Minimum Path SumGrid path DP (right/down accumulation)