A Complete Guide

Whether you’re prepping for coding interviews or honing your algorithmic thinking, LeetCode Problem 62: Unique Paths is a must-know dynamic programming (DP) challenge. In this step-by-step guide, we’ll walk you through the logic behind the solution, break down the dynamic programming approach, and provide clean Java code to implement it. Let’s get started!

🚀 Problem Overview: Navigating a Grid

You’re given an m x n grid. A robot starts at the top-left corner and wants to reach the bottom-right corner. The robot can only move right or down.

Example:
In a 3x7 grid, the robot can take 28 unique paths. But how do we calculate that efficiently—especially for larger grids?

🧠 Why Use Dynamic Programming?

This problem has two hallmarks of dynamic programming:

• Overlapping subproblems: The number of paths to a cell depends on the number of paths to adjacent cells.
• Optimal substructure: The solution to the whole problem is built from optimal solutions to smaller subproblems.

Rather than recomputing results, we store them in a DP table, cutting down redundant calculations.

🛠️ Step-by-Step DP Solution

1. Define a DP Table

Let dp[i][j] represent the number of unique ways to reach cell (i, j).

2. Initialize the Edges

• The first row and column are set to 1, since there’s only one way to reach them: all right or all down moves.

3. Fill in the Table

Each inner cell’s value is the sum of the paths from:

• The cell above it: dp[i-1][j]
• The cell to the left: dp[i][j-1]

4. Return the Final Answer

The result is in the bottom-right cell: dp[m-1][n-1].

✅ Java Implementation

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

        // Initialize first row and column
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;

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

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

📊 Time & Space Complexity

• Time: O(m × n) — every cell is visited once.
• Space: O(m × n) — for the 2D table.
  (You can optimize this to O(n) using a 1D array if needed.)

🧩 Visual Walkthrough: 3×3 Grid

• Answer: dp[2][2] = 6 unique paths.

🔁 Bonus: Combinatorics Approach

There’s a mathematical shortcut! The robot must make (m-1) downs and (n-1) rights—(m+n-2) total moves.

Use the combination formula:

• Time: O(min(m, n))
• Space: O(1)

This is more efficient, but the DP method is easier to grasp—especially for beginners.

🏁 Conclusion

The Unique Paths problem is a great introduction to dynamic programming on grids. It teaches you how to break down complex problems using smaller subproblems and build up a solution iteratively.

🚧 Next Challenge:

Try Unique Paths II, where obstacles are added. Or practice with similar problems like:

• Minimum Path Sum
• Climbing Stairs
• Edit Distance

Keep practicing, and you’ll be a DP pro in no time!