Unique Paths

Problem Statement

In this problem, we encounter a robot situated at the top-left corner of an m x n grid. The goal for the robot is to traverse to the bottom-right corner of this grid. However, the robot has limited movement options; it can only move either to the right or downwards at each step. Given these two dimensions, m and n, the task is to determine all possible unique paths from the top-left to the bottom-right corner of the grid. The solutions need to fit within computational limits, specifically ensuring that the number of paths does not exceed 2 x 10^9.

Examples

Example 1

Input:

m = 3, n = 7

Output:

28

Example 2

Input:

m = 3, n = 2

Output:

3

Explanation:

From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints

• 1 <= m, n <= 100

Approach and Intuition

To solve this problem, we can use the concept of combinatory mathematics or dynamic programming.

• Combinatory Approach:

  1. Realize that any path from the top-left corner to the bottom-right corner in an m x n grid consists of exactly m-1 moves down and n-1 moves right, irrespective of order.
  2. The problem then reduces to finding the number of unique ways to rearrange m-1 downs and n-1 rights.
  3. This can be solved using combinations: C(m+n-2, m-1) or C(m+n-2, n-1), where C(n, k) represents the number of ways to choose k items from n items without regard to order.

• Dynamic Programming Approach:

  1. Use a 2D array dp where dp[i][j] represents the number of ways to reach cell (i, j) from the top-left corner (0,0).
  2. Initialize dp[0][0] to 1 since there's only one way to be at the starting position.
  3. For each cell (i, j), the robot could have moved from the left (i, j-1) or from above (i-1, j).
  4. Thus, the value of dp[i][j] is the sum of dp[i-1][j] and dp[i][j-1].
  5. The value in dp[m-1][n-1] will give the total number of unique paths from the top-left to the bottom-right corner.

Examples Explained:

• In the first example (m = 3, n = 7):

  • The dynamic programming approach would create a 3 x 7 matrix and iteratively fill up the matrix to find 28 unique paths.
  • Combinatorially, C(3+7-2, 3-1) = C(8, 2) = 28 unique paths.

• In the second example (m = 3, n = 2), evaluating DP matrix or combinatorics alike, we'd compute C(3+2-2, 3-1) = C(3, 2) = 3 possible paths, enumerated in the explanation provided.

Solutions

class Solution {
public:
    int countPaths(int rows, int cols) {
        vector<vector<int>> grid(rows, vector<int>(cols, 1));
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                grid[row][col] = grid[row - 1][col] + grid[row][col - 1];
            }
        }
        return grid[rows - 1][cols - 1];
    }
};