Crack the Backend

Problem Statement

A robot is located at the top-left corner of an m x n grid. The robot can only move right or down at any point. How many possible unique paths are there for the robot to reach the bottom-right corner?

The grid has m rows and n columns; the robot starts at (0, 0) and must reach (m-1, n-1).
Only right and down moves are allowed, so we need exactly (m-1) + (n-1) steps. This is a classic 2D DP (or combinatorial: the answer is C(m+n-2, m-1)).

Key Observations

Define dp[i][j] = number of ways to reach cell (i, j) from (0, 0). To reach (i, j), the last step was either from (i-1, j) (down) or (i, j-1) (right). So dp[i][j] = dp[i-1][j] + dp[i][j-1].
Base: dp[0][0] = 1, and the first row dp[0][j] = 1 (only one way: all right), first column dp[i][0] = 1 (all down). Then fill row by row or column by column.
Space can be reduced to O(n) by using a single row and updating in place: dp[j] += dp[j-1] for j >= 1.

Approach

High-level: dp[i][j] = number of paths from (0,0) to (i,j). dp[i][j] = dp[i-1][j] + dp[i][j-1] with first row and first column set to 1.

Steps:

dp[j] = 1 for all j (first row). For i = 1..m-1: for j = 1..n-1, dp[j] += dp[j-1].
Return dp[n-1] (bottom-right).

Implementation

Java

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

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

    return dp[n - 1];
}

Test Cases

Example 1

Input

m = 3, n = 7

Expected

28

Explanation

28 unique paths.

Complexity Analysis

Time: O(m*n).
Space: O(n) with one row.

Follow-ups

Unique Paths II: grid has obstacles (some cells blocked).