14.6 Unique Paths

14.6.1 Problem Metadata

14.6.2 Description

A robot can move only right or down on an m x n grid from the top-left to the bottom-right. Count the number of unique paths.

14.6.3 Examples

Input: m = 3, n = 7
Output: 28

14.6.4 Constraints

  • 1 <= m, n <= 100

14.6.5 Solution - DP Grid

14.6.5.1 Walkthrough

Paths to (i, j) equal the sum of paths to (i-1, j) and (i, j-1) since those are the only ways to enter. Initialize the first row and column to 1 because there is only one way to reach those cells.

14.6.5.2 Analysis

  • Time Complexity: O(m * n)
  • Space Complexity: O(m * n) (or O(n) with rolling arrays)

14.6.5.3 Implementation Steps

  1. Fill a DP matrix with dp[0][*] = dp[*][0] = 1.
  2. For each cell from (1,1) to (m-1,n-1) compute dp[i][j] = dp[i-1][j] + dp[i][j-1].
  3. Return dp[m-1][n-1].

14.6.5.4 Code - Java

public 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];
}