62. Unique Paths - Detailed Explanation

Problem Statement

You are given two integers, m and n, which represent the dimensions of an m x n grid. A robot is initially located in the top-left corner of this grid (cell (0, 0)). The robot can only move either down or right at any point in time. The goal is for the robot to reach the bottom-right corner of the grid (cell (m - 1, n - 1)). Your task is to determine how many unique paths exist for the robot to get from the top-left corner to the bottom-right corner.

Example 1

• Input:
  m = 3, n = 7
• Output:
  28
• Explanation:
  There are 28 distinct ways for the robot to reach the bottom-right corner by only moving right or down.

Example 2

• Input:
  m = 3, n = 2
• Output:
  3
• Explanation:
  The three unique paths are:
  1. Right → Down → Down
  2. Down → Down → Right
  3. Down → Right → Down

Example 3

• Input:
  m = 7, n = 3
• Output:
  28
• Explanation:
  Similarly, there are 28 distinct ways for the robot to move from (0,0) to (6,2) using only right and down moves.

Hints and Intuition

• Hint 1:
  Think about breaking down the problem into subproblems. At any given cell, the number of ways to reach that cell is the sum of the ways to get to the cell above it and the ways to get to the cell on its left.

• Hint 2:
  Consider using dynamic programming (DP) to build up a solution for the entire grid. Alternatively, notice that the robot must make exactly (m-1) down moves and (n-1) right moves in some order, which leads to a combinatorial solution.

Detailed Approaches

Approach A: Dynamic Programming

Idea

• Create a 2D DP array dp where dp[i][j] represents the number of unique paths to cell (i, j).
• Base Cases:
  • The starting cell dp[0][0] is 1 (only one way to be at the start).
  • For the first row (i = 0), there is only one way to move (all rights) so dp[0][j] = 1.
  • For the first column (j = 0), there is only one way to move (all downs) so dp[i][0] = 1.
• Recurrence:
  For any cell (i, j), the number of paths to reach it is:

  dp[i][j] = dp[i-1][j] + dp[i][j-1]
  

  This is because the robot can only come from the top or the left.

Walkthrough

1. Initialization:
   Create a grid dp of size m x n. Initialize the first row and first column to 1.
2. Fill the DP Table:
   For each cell (i, j) starting from (1, 1), compute dp[i][j] using the recurrence.
3. Final Answer:
   The value at dp[m-1][n-1] is the number of unique paths from the start to the finish.

Approach B: Combinatorial Mathematics

Idea

• To reach the bottom-right corner, the robot must make exactly (m-1) downs and (n-1) rights in any order.
• The total number of moves required is (m-1 + n-1) = (m+n-2).
• The problem reduces to finding the number of distinct arrangements of these moves, which is given by the binomial coefficient:

  Number of unique paths = C(m+n-2, m-1) = (m+n-2)! / [(m-1)! * (n-1)!]
  

Walkthrough

1. Total Moves:
   Calculate the total number of moves (m+n-2).
2. Choose Moves:
   Choose which moves are downs (or rights). The answer is the number of ways to choose (m-1) moves from (m+n-2).
3. Final Answer:
   Compute the binomial coefficient to get the answer.

Code Implementation

Python Implementation (Dynamic Programming)