Leetcode Link

To understand this problem, let’s begin by considering a simple example: a 2x2 maze. In this maze, you can only move right or down. To reach the bottom-right corner ([1, 1]), there are two possible paths:

  1. Right → Down
  2. Down → Right

Thus, we can conclude that for a 2x2 maze, there are 2 unique paths to reach the bottom-right corner.

Extending to Larger Grids

Let’s consider a larger grid, such as a 3x7 maze. We can construct a matrix to represent the number of ways to reach each cell. The key observation here is:

The number of ways to reach a cell [i, j] is the sum of the number of ways to reach the cell directly above it ([i-1, j]) and the cell directly to its left ([i, j-1]).

Step-by-Step Construction

  1. Start by initializing the grid. Each cell in the first row and first column has only one way to be reached since you can only move right or down:
1, 1, 1, 1, 1, 1, 1
1,
1,

  1. Now, compute the value for each cell based on the formula:

    • For cell [1, 1]:
      m[1][1] = m[0][1] + m[1][0] = 1 + 1 = 2
      Updated matrix:
      1, 1, 1, 1, 1, 1, 1
      1, 2
      1,

  2. Continue filling the matrix:

    • For cell [2, 1]:
      m[2][1] = m[1][1] + m[2][0] = 2 + 1 = 3
    • For cell [1, 2]:
      m[1][2] = m[0][2] + m[1][1] = 1 + 2 = 3

    Updated matrix:

    1, 1, 1, 1, 1, 1, 1
    1, 2, 3
    1, 3

  3. By repeating this process, we can eventually fill the entire grid. For a 3x7 grid, the completed matrix looks like this:

1, 1, 1, 1, 1, 1, 1
1, 2, 3, 4, 5, 6, 7
1, 3, 6, 10, 15, 21, 28

Final Answer

The value at the bottom-right corner of the matrix represents the total number of unique paths. For a 3x7 grid, there are 28 unique paths.

This approach can be generalized for any grid size using dynamic programming. By constructing a matrix and filling it based on the relationship between adjacent cells, you can efficiently compute the number of unique paths for any m x n grid.