Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Unique Paths

Unique Paths

Master this topic with zero to advance depth.

Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (grid[0][0]). The robot tries to move to the bottom-right corner (grid[m-1][n-1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Visual Representation

m=3, n=2 Grid: (S) (1) (S=Start, E=End) (1) (1) (1) (E) Paths: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down Total: 3
Medium

Examples

Input: m = 3, n = 2
Output: 3

From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

  1. Right -> Down -> Down
  2. Down -> Down -> Right
  3. Down -> Right -> Down
Input: m = 3, n = 7
Output: 28
Approach 1

Level I: Dynamic Programming (2D)

Intuition

The number of ways to reach cell (i, j) is the sum of ways to reach the cell above it (i-1, j) and the cell to its left (i, j-1).

Thought Process

  1. dp[i][j] = dp[i-1][j] + dp[i][j-1].
  2. Base cases: dp[0][j] = 1 and dp[i][0] = 1 because there is only one way to move along the edges (straight right or straight down).
⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

m=3, n=3

RowCol 0Col 1Col 2Action
0111Init Row 0
11231+1=2, 2+1=3
21361+2=3, 3+3=6
java
public class Main {
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else 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
    }
}
Approach 2

Level II: Memoization (Top-Down Recursion)

Intuition

The recursive brute force for grid path counting has overlapping subproblems. We cache each (i, j) state so we never recompute it.

Visual

Memo Grid (m=3, n=3): | 0 | 1 | 1 | | 1 | 2 | ? | <- memo[1][2] reused by (2,2) | 1 | ? | ? |
⏱ O(M * N)💾 O(M * N) memo + O(M+N) stack

Detailed Dry Run

m=3, n=3. memo[2][2] = memo[1][2] + memo[2][1]. Both sub-calls are cached after first computation.

java
public class Main {
    static int[][] memo;
    public static int solve(int m, int n) {
        if (m == 1 || n == 1) return 1;
        if (memo[m][n] != 0) return memo[m][n];
        return memo[m][n] = solve(m - 1, n) + solve(m, n - 1);
    }

    public static int uniquePaths(int m, int n) {
        memo = new int[m + 1][n + 1];
        return solve(m, n);
    }

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

Level III: Space Optimized (1D)

Intuition

To compute dp[i][j], we only need the value above it dp[i-1][j] (from the previous row) and the value to its left dp[i][j-1] (already computed in the current row). We can use a single row array.

Logic Steps

  1. Initialize a row array of size n with 1s.
  2. Iterate m-1 times (for all rows except the first).
  3. For each row, iterate through columns 1 to n-1:
    • row[j] = row[j] + row[j-1].
  4. Return row[n-1].
⏱ O(M * N)💾 O(N)

Detailed Dry Run

m=3, n=3

Actionrow array
Init[1, 1, 1]
Row 1[1, (1+1)=2, (2+1)=3]
Row 2[1, (1+2)=3, (3+3)=6]
java
import java.util.Arrays;

public class Main {
    public static int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                row[j] += row[j - 1];
            }
        }
        return row[n - 1];
    }

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

⚠️ Common Pitfalls & Tips

Ensure the loop for columns starts at 1, as the first column always has 1 path (staying at the left edge).

← Previous QuestionLongest Increasing Subsequence
Next Question →Coin Change