Problem Statement

A robot is located at the top-left corner of an m x n grid (marked as (0,0)).

The robot can only move either down or right at any point in time.
The robot is trying to reach the bottom-right corner of the grid (marked as (m-1, n-1)).

Return the number of possible unique paths that the robot can take to reach the destination.

---

Example 1

Input:

m = 3, n = 7

Output:

28

Explanation:
There are 28 different paths from top-left to bottom-right if the robot can only move down or right.

---

Example 2

Input:

m = 3, n = 2

Output:

3

Explanation:
Paths are:

1. Right → Down → Down
2. Down → Right → Down
3. Down → Down → Right

---

Constraints

• 1 <= m, n <= 100
• The answer will be less than or equal to 2 * 10^9.

---

Approach 1: Dynamic Programming (Tabulation)

This is a classic combinatorial dynamic programming problem.

We can model the grid as a 2D DP table, where each cell dp[i][j] represents the number of ways to reach that cell from (0,0).

Key Observations

1. The robot can only come to (i, j) from:
   • Above: (i-1, j)
   • Left: (i, j-1)
2. Therefore,
   dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. Base case:
   • There is only one way to reach any cell in the first row or first column — by moving only right or only down.
   • So dp[i][0] = 1 and dp[0][j] = 1.

---

Step-by-Step Solution

1. Create a 2D array dp[m][n].
2. Initialize the first row and first column with 1s.
3. Fill the remaining cells using the recurrence relation.
4. The answer will be dp[m-1][n-1].

---

Java Implementation

public class UniquePaths {

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

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

        // Step 2: Fill the rest of the grid
        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];
            }
        }

        // Step 3: Return the bottom-right corner value
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        UniquePaths solver = new UniquePaths();
        System.out.println(solver.uniquePaths(3, 7)); // Output: 28
        System.out.println(solver.uniquePaths(3, 2)); // Output: 3
    }
}

---

Dry Run Example (m=3, n=3)

Grid size: 3 x 3

Cell	dp value	Explanation
(0,0)	1	Starting point
(0,1)	1	Only right move possible
(0,2)	1	Only right move possible
(1,0)	1	Only down move possible
(1,1)	2	From top (1) + from left (1)
(1,2)	3	From top (1) + from left (2)
(2,0)	1	Only down move possible
(2,1)	3	From top (2) + from left (1)
(2,2)	6	From top (3) + from left (3)

Final answer: dp[2][2] = 6

So, there are 6 unique paths in a 3×3 grid.

---

Approach 2: Space Optimized DP

We only need the previous row to calculate the current row.
So instead of using a 2D array, we can use a 1D array.

Java Implementation (Optimized)

public class UniquePathsOptimized {

    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] + dp[j - 1];
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        UniquePathsOptimized solver = new UniquePathsOptimized();
        System.out.println(solver.uniquePaths(3, 7)); // Output: 28
        System.out.println(solver.uniquePaths(3, 2)); // Output: 3
    }
}

---

Time and Space Complexity

Operation	Complexity	Explanation
Time	O(m * n)	Each cell is computed once
Space (2D DP)	O(m * n)	Storing all cells
Space (Optimized DP)	O(n)	Using single array

---

Approach 3: Combinatorial Formula (Mathematical Solution)

To reach the bottom-right corner, you need to take exactly:

• (m - 1) down moves, and
• (n - 1) right moves.

Total moves = (m + n - 2)

We just need to choose where the down (or right) moves happen among all moves.

Hence, number of paths =
C(m + n – 2, m – 1) = (m + n - 2)! / ((m - 1)! * (n - 1)!)

---

Java Implementation (Combinatorial)

public class UniquePathsCombinatorial {

    public int uniquePaths(int m, int n) {
        long result = 1;
        int totalMoves = m + n - 2;
        int downMoves = Math.min(m - 1, n - 1); // choose smaller for efficiency

        for (int i = 1; i <= downMoves; i++) {
            result = result * (totalMoves - downMoves + i) / i;
        }

        return (int) result;
    }

    public static void main(String[] args) {
        UniquePathsCombinatorial solver = new UniquePathsCombinatorial();
        System.out.println(solver.uniquePaths(3, 7)); // Output: 28
        System.out.println(solver.uniquePaths(10, 10)); // Output: 48620
    }
}

---

Advantages of Combinatorial Approach

• Extremely fast — runs in O(min(m, n))
• No DP array required.
• Handles large grids efficiently.

---

Key Takeaways

1. The problem can be solved in three main ways:
   • Dynamic Programming (2D) — simple and intuitive.
   • Space-Optimized DP (1D) — efficient and elegant.
   • Combinatorial Formula — mathematically optimal.
2. The core idea is that every move is either right or down, and the total number of unique paths equals the number of unique move sequences.
3. The combinatorial approach is ideal for large grids, while DP is great for conceptual understanding and interviews.