Course contentsShow
← Computer Science
Lesson 940 of 2,87222. Dynamic ProgrammingFree lesson

Unique Paths in Grid

Count unique paths from top-left to bottom-right in a grid moving only right or down.

Unique Paths in Grid

You'll learn how to count all distinct routes through a grid using dynamic programming.

Imagine you're standing at the top-left corner of a city grid and need to reach the bottom-right corner. You can only move right or down (never left or up). How many different routes can you take?

The Core Idea

Given an m x n grid, you start at position (0, 0) and want to reach (m-1, n-1). At each cell, you have at most two choices: move right or move down. The problem asks: how many unique paths exist?

This is a classic dynamic programming problem because:

  • Optimal substructure: The number of ways to reach any cell depends on the number of ways to reach the cells directly above it and to its left
  • Overlapping subproblems: We'll recompute paths to the same cells multiple times if we use naive recursion

The DP Approach

Define dp[i][j] = number of unique paths to reach cell (i, j).

Base cases:

  • dp[0][j] = 1 for all columns (only one way: keep moving right)
  • dp[i][0] = 1 for all rows (only one way: keep moving down)

Transition:

  • dp[i][j] = dp[i-1][j] + dp[i][j-1]

You can reach cell (i, j) either from the cell above or from the cell to the left, so you add those possibilities.

Think of it like water flowing down: each cell accumulates all the paths that can flow into it from above and from the left.

Key Takeaway: The Unique Paths problem uses dynamic programming to efficiently count routes by recognizing that paths to any cell equal the sum of paths to its top and left neighbors.