Unique Paths in a Grid
Imagine a robot starting at the top-left corner of a grid and wanting to reach the bottom-right corner. The robot can only move down or right at any point in time. This problem asks us to calculate the total number of distinct paths the robot can take to reach its destination. This is a classic combinatorial problem that can be solved efficiently using dynamic programming or mathematical formulas.
Problem Description
You are given a grid of dimensions m rows and n columns. A robot is positioned at the top-left cell (row 0, column 0) and its goal is to reach the bottom-right cell (row m-1, column n-1). The robot can only perform two types of movements: move one step down or move one step right.
Your task is to determine the total number of unique paths the robot can take from the starting cell to the destination cell.
Key Requirements:
- Calculate the total number of distinct paths.
- The robot must always stay within the bounds of the
m x ngrid. - The robot can only move down or right.
Expected Behavior:
The function should return a single integer representing the total count of unique paths.
Edge Cases:
- A 1x1 grid.
- A grid with only one row or one column.
Examples
Example 1:
Input: m = 3, n = 7
Output: 28
Explanation: From the 3x7 grid, there are 28 distinct paths for the robot to reach the bottom-right corner from the top-left corner.
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation:
The paths are:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Example 3:
Input: m = 1, n = 1
Output: 1
Explanation: In a 1x1 grid, the robot is already at the destination. There is only one path (doing nothing).
Constraints
- 1 <=
m<= 100 - 1 <=
n<= 100 mandnare integers.- The solution should be efficient, aiming for a time complexity better than brute-force enumeration of all paths.
Notes
Consider how the number of paths to any cell in the grid depends on the number of paths to the cells from which it can be reached. This hints at a dynamic programming approach. Alternatively, think about the total number of moves required and how many of them must be "down" and how many must be "right".