Unique Paths in Grid

From top-left to bottom-right of an m × n grid, moving only right or down, how many distinct routes exist? This is the classic grid counting DP pattern — the foundation for weighted paths, obstacles, and advanced variants. This lesson covers Unique Paths I (LeetCode 62), Unique Paths II (63), combinatorics, space optimization, cherry pickup & dungeon game extensions, with C, Java, and Python code and trace tables. For min-cost / max-reward grids, see Travel & candies.

Overview

Every cell (i, j) can be reached only from the cell above (i−1, j) or from the left (i, j−1). The number of paths to a cell is the sum of paths from those two predecessors.

3×3 grid — only right (→) and down (↓):

  Start → →
          ↓ ↓
            ↓ End

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

First row & first column: all 1s (only one way along each edge)
Answer: dp[m-1][n-1]

Unique Paths I — Count Routes

Problem (LeetCode 62): Given m rows and n columns with no obstacles, return the number of unique paths from (0, 0) to (m−1, n−1).

State: dp[i][j] = number of distinct paths to reach cell (i, j).

Base cases: dp[0][j] = 1 and dp[i][0] = 1 for all valid i, j.

Complexity: O(m·n) time, O(m·n) space (reducible to O(n)).

Unique Paths I Code (C, Java, Python)

Python

def unique_paths(m, n):
    """LeetCode 62 — count paths in m x n grid. O(m*n) time."""
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]


if __name__ == "__main__":
    tests = [(3, 7), (3, 2), (3, 3)]
    for m, n in tests:
        print(f"uniquePaths({m}, {n}) → {unique_paths(m, n)}")

Java

public class UniquePathsI {

    /** Count unique paths — bottom-up 2D DP. */
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 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];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // 28
        System.out.println(uniquePaths(3, 2)); // 3
        System.out.println(uniquePaths(3, 3)); // 6
    }
}

C

#include <stdio.h>

#define MAX 100

int unique_paths(int m, int n) {
    int dp[MAX][MAX];
    int i, j;

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

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

int main(void) {
    printf("%d\n", unique_paths(3, 7)); /* 28 */
    printf("%d\n", unique_paths(3, 2)); /* 3 */
    printf("%d\n", unique_paths(3, 3)); /* 6 */
    return 0;
}

Unique Paths I Output & Trace

Program output

DP table trace for 3×3 grid

Cell (2,2): paths = from top (3) + from left (3) = 6.

Combinatorics Shortcut

To reach the bottom-right from top-left you need exactly m−1 down moves and n−1 right moves — m+n−2 total steps. Choose which steps are “down”:

Answer = C(m+n−2, m−1) = C(m+n−2, n−1)

def unique_paths_comb(m, n):
    """LeetCode 62 — combinatorics O(min(m,n)) with multiplicative formula."""
    from math import comb
    return comb(m + n - 2, m - 1)


def unique_paths_comb_no_math(m, n):
    """Avoid large factorials — multiply/divide in loop."""
    if m > n:
        m, n = n, m  # C(a,b) with b = min(m-1, n-1)
    result = 1
    for i in range(1, m):
        result = result * (n - 1 + i) // i
    return result

Unique Paths II — With Obstacles

Problem (LeetCode 63): Grid contains obstacles marked as 1 (blocked). Free cells are 0. Return the number of unique paths. If start or end is blocked, return 0.

Recurrence: If grid[i][j] == 1, then dp[i][j] = 0. Otherwise same sum from top and left.

Edge case: If grid[0][0] == 1, return 0 immediately.

Unique Paths II Code (C, Java, Python)

Python

def unique_paths_with_obstacles(grid):
    """LeetCode 63 — count paths avoiding obstacles."""
    if not grid or grid[0][0] == 1:
        return 0
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    dp[0][0] = 1
    for j in range(1, n):
        dp[0][j] = 0 if grid[0][j] == 1 else dp[0][j - 1]
    for i in range(1, m):
        dp[i][0] = 0 if grid[i][0] == 1 else dp[i - 1][0]

    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]


if __name__ == "__main__":
    grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
    print(unique_paths_with_obstacles(grid))  # 2

Java

public class UniquePathsII {

    public static int uniquePathsWithObstacles(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0][0] == 1) return 0;
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = 1;
        for (int j = 1; j < n; j++) {
            dp[0][j] = grid[0][j] == 1 ? 0 : dp[0][j - 1];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0] = grid[i][0] == 1 ? 0 : dp[i - 1][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j] == 1) dp[i][j] = 0;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        System.out.println(uniquePathsWithObstacles(grid)); // 2
    }
}

C

#include <stdio.h>

#define MAX 100

int unique_paths_obstacles(int grid[MAX][MAX], int m, int n) {
    int dp[MAX][MAX];
    int i, j;

    if (grid[0][0] == 1) return 0;

    dp[0][0] = 1;
    for (j = 1; j < n; j++)
        dp[0][j] = grid[0][j] == 1 ? 0 : dp[0][j - 1];
    for (i = 1; i < m; i++)
        dp[i][0] = grid[i][0] == 1 ? 0 : dp[i - 1][0];

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            if (grid[i][j] == 1) dp[i][j] = 0;
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

int main(void) {
    int grid[MAX][MAX] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    printf("%d\n", unique_paths_obstacles(grid, 3, 3)); /* 2 */
    return 0;
}

Unique Paths II Output & Trace

Program output

DP trace for [[0,0,0],[0,1,0],[0,0,0]]

Space Optimization — 1 Row DP

Each cell depends only on the current row and the row above. Keep one row of length n and update in place left-to-right:

def unique_paths_1row(m, n):
    """LeetCode 62 — O(n) space using single row."""
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]
    return row[n - 1]


def unique_paths_obstacles_1row(grid):
    """LeetCode 63 — O(n) space."""
    if not grid or grid[0][0] == 1:
        return 0
    m, n = len(grid), len(grid[0])
    row = [0] * n
    row[0] = 1
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                row[j] = 0
            elif j > 0:
                row[j] += row[j - 1]
    return row[n - 1]

Extended Grid Variants

Once you know the counting template, harder problems add dimensions, direction constraints, or backward DP.

Cherry Pickup (LeetCode 741)

Collect max cherries going start→end, then return end→start (both only right/down). Two travelers moving in sync can be modeled as one 3D state dp[r1][c1][r2] with c2 = r1+c1−r2, or solve forward max path + backward max path and combine at each cell.

Dungeon Game (LeetCode 174)

Each cell changes health. Find minimum initial health to reach princess at bottom-right alive (health > 0 at all times). Work backward from the goal:

def calculate_minimum_hp(dungeon):
    """LeetCode 174 — backward DP from bottom-right."""
    m, n = len(dungeon), len(dungeon[0])
    dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    dp[m][n - 1] = dp[m - 1][n] = 1  # border sentinels

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
            dp[i][j] = max(1, need)
    return dp[0][0]

Out of Boundary Paths (LeetCode 576)

Count paths that leave an m × n grid in exactly k moves (can move in all 4 directions). State: memo[i][j][steps] — classic top-down DP with modulo 10⁹+7.

DP vs Combinatorics

• Empty grid: Combinatorics C(m+n−2, m−1) is fastest — mention it after writing DP.
• Obstacles / blocked cells: Combinatorics breaks — must use DP (or inclusion-exclusion, rarely in interviews).
• Weighted grids: Switch from sum to min/max — same traversal order, different merge.
• Teaching order: DP first (general), combinatorics as optimization for the special case.

Approach Comparison

Real-Life Applications

Interview Tips

1. State the recurrence aloud: dp[i][j] = dp[i−1][j] + dp[i][j−1] before coding.
2. Initialize first row and column to 1 (or 0 if obstacle on that edge).
3. For obstacles: if grid[i][j] == 1, set dp[i][j] = 0 — do not add from neighbors.
4. Mention combinatorics for LeetCode 62 — shows math maturity.
5. Offer O(n) space optimization after the 2D solution works.
6. Trace a 3×3 table on the whiteboard — interviewers love seeing 1,1,1 → 1,2,3 → 1,3,6.
7. Distinguish count (this page) from min/max cost (Travel & candies).
8. For dungeon game: explain why backward DP is natural (need to know future health requirement).