Unique Paths – 62. LeetCode

The Unique Paths problem asks us to find the number of distinct ways to reach the bottom-right corner of a grid starting from the top-left corner. You can only move right or down at any step. This problem is a great example of combinatorics, recursion, and dynamic programming.

Imagine you’re navigating a maze-like grid, and your goal is to count all possible paths without retracing your steps. This problem teaches important problem-solving techniques and optimization strategies for real-world applications, such as logistics or robotics pathfinding.

Brute Force

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        return findPaths(0, 0, m, n);
    }

    private int findPaths(int i, int j, int m, int n) {
        // Base case: Reached the bottom-right corner
        if (i == m - 1 && j == n - 1) return 1;
        // Out of bounds
        if (i >= m || j >= n) return 0;
        // Recurse by moving right and down
        return findPaths(i + 1, j, m, n) + findPaths(i, j + 1, m, n);
    }
}

• Starts from (0, 0) and recursively explores all possible moves (right and down) until reaching the bottom-right corner.

• The base case ensures that valid paths are counted, while invalid paths (out of bounds) return 0.

Optimized Approach: Dynamic Programming

The grid-like structure of this problem makes it an ideal candidate for 2D DP. Each cell in the grid depends on the paths leading to it, creating overlapping subproblems that can be solved efficiently using DP.

We’ll use a 2D DP table to solve the problem, where each entry represents the number of unique paths to reach that specific cell. Let’s break the solution into intuitive steps.

1. The DP Table

• Structure: The DP table is a 2D array dp[m][n], where dp[i][j] represents the number of ways to reach cell (i, j) in the grid.

• Goal: Populate this table such that the value at dp[m-1][n-1] (bottom-right corner) represents the total number of unique paths.

2. Base Cases

To handle edge cases:

• First Row: dp[0][j] = 1 for all j. There’s only one way to traverse the first row: keep moving right.

• First Column: dp[i][0] = 1 for all i. Similarly, there’s only one way to traverse the first column: keep moving down.

3. Transition Relation

For all other cells (i, j):

• The value of dp[i][j] is the sum of:

• The value in the cell directly above it (dp[i-1][j]).

• The value in the cell directly to the left of it (dp[i][j-1]).

• Formula:  dp[i][j] = dp[i-1][j] + dp[i][j-1] .

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

Line-By-Line Explanation

Step 1: Initialize 2D Array

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

• Initializes a 2D array dp of size m x n to store intermediate results. Each entry dp[i][j] will represent the number of unique paths to cell (i, j).

Step 2: Initialize the First Column

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

• Sets all values in the first columns of the dp table to 1.
• The base case for cells in the first column is straightforward: since no rightward movement is allowed, the only valid path is downward.

Step 3: Initialize the First Row

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

• Sets all values in the first row of the dp table to 1.

Step 4: Fill the DP Table

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

• Uses nested loops to fill the rest of the dp table.
• For each cell (i, j), calculates dp[i][j] as the sum of:
  • The number of paths to the cell directly above it
  • The number of paths to the cell directly to its left

Step 5: Return the Result

return dp[m-1][n-1];

• Returns the value stores at dp[m – 1][n – 1], which represents the total number of unique paths to the bottom-right corner of the grid.

Why This Code Works

This code effectively solves the Unique Paths problem using a 2D dynamic programming approach, balancing clarity, efficiency, and adherence to best practices. It demonstrates how DP systematically breaks down a problem into smaller subproblems, efficiently storing results to avoid redundant calculations.