Blind 75Medium

Unique Paths — Grid Dynamic Programming

Count paths from top-left to bottom-right by summing ways from the top and left neighbors.

Dynamic ProgrammingGrid

View problem on LeetCode

Problem Statement

Given an m × n grid, compute how many unique paths exist when you may only move down or right.

Why This Problem Matters

Classic combinatorics DP that introduces state recurrence on grids.
Teaches reuse of prefix sums and overlaps with Pascal’s triangle reasoning.
Forms the base for obstacles and minimum path sum variants.

Thought Process

Define state clearly

dp[r][c] represents number of ways to reach cell (r, c). The recurrence dp[r][c] = dp[r-1][c] + dp[r][c-1].

Initialise first row and column

Only one way to move straight right or straight down along edges.

Space-optimise if desired

Reuse a single row/column vector because each state depends only on immediate neighbors.

Step-by-Step Reasoning

Create dp array sized m × n initialised to 1 for first row/column.
For r from 1..m-1 and c from 1..n-1 set dp[r][c] = dp[r-1][c] + dp[r][c-1].
Return dp[m-1][n-1].

Dry Run

m = 3, n = 7

DP builds Pascal triangle values culminating in 28 routes.

m = 1 or n = 1

Only one path exists because movement is restricted to one direction.

Complexity Analysis

Time

O(m·n)

Space

O(n)

Why

Two nested loops; space can drop to O(n) with a rolling array.

Annotated Solution

JAVA

public class UniquePaths {
  public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    for (int c = 0; c < n; c += 1) {
      dp[c] = 1;
    }

    for (int r = 1; r < m; r += 1) {
      for (int c = 1; c < n; c += 1) {
        dp[c] += dp[c - 1];
      }
    }

    return dp[n - 1];
  }
}

Using a single row keeps space minimal; dp[c] represents the number of ways to reach the current cell.

Common Pitfalls

Failing to initialise edges breaks the recurrence because they default to zero.
Using int may overflow for large grids; mention combinatorial formula or BigInteger if needed.
Mixing up indices when converting between 0-based arrays and grid coordinates.

Follow-Up Questions

How do obstacles change the recurrence?
Can you derive the combinatorial formula C(m+n-2, m-1) directly?

Key Takeaways

Grid DP often reduces to adding results from adjacent states.

Space optimisation via rolling arrays is a common interview follow-up.

Remember the combinatorial interpretation to impress interviewers.