Unique Paths
Problem Statement
A robot is located at the top-left corner of a m x n grid. 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. How many possible unique paths are there?
Constraints:
- 1 <= m, n <= 100
- The answer will be less than or equal to 2 * 10^9
- Test cases are generated so that the answer will fit in a 32-bit integer
Input Format:
- Two integers m and n representing the grid dimensions
- m represents the number of rows
- n represents the number of columns
Output Format:
- Return the number of possible unique paths that the robot can take to reach the bottom-right corner
Examples:
Example 1:
Input:
m = 3, n = 7
Output:
28
Explanation:
From the top-left corner, there are a total of 28 ways to reach the bottom-right corner when moving only right and down.
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 -> Right -> Down 3. Down -> Down -> Right
Example 3:
Input:
m = 7, n = 3
Output:
28
Explanation:
This is symmetric to the first example. There are 28 ways to reach the bottom-right corner.
Solutions
Dynamic Programming Approach
Use a 2D array where dp[i][j] represents the number of unique paths to reach position (i, j). Each cell's value is the sum of the paths from the cell above and the cell to the left.
Space-Optimized Dynamic Programming
Since each cell only depends on the cell above and to the left, we can use a 1D array to keep track of the paths for the current row.
Combinatorial Solution
This problem can be solved using combinatorics. The robot needs to move right (n-1) times and down (m-1) times. So the total number of paths is (m+n-2) choose (m-1).
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Create a 3x7 grid initialized with 1s for the first row and column.
- dp = [[1, 1, 1, 1, 1, 1, 1], [1, ?, ?, ?, ?, ?, ?], [1, ?, ?, ?, ?, ?, ?]]
- Fill in dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
- Fill in dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
- Fill in dp[1][3] = dp[0][3] + dp[1][2] = 1 + 3 = 4
- Fill in dp[1][4] = dp[0][4] + dp[1][3] = 1 + 4 = 5
- Fill in dp[1][5] = dp[0][5] + dp[1][4] = 1 + 5 = 6
- Fill in dp[1][6] = dp[0][6] + dp[1][5] = 1 + 6 = 7
- Fill in dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
- Fill in dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
- Fill in dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10
- Fill in dp[2][4] = dp[1][4] + dp[2][3] = 5 + 10 = 15
- Fill in dp[2][5] = dp[1][5] + dp[2][4] = 6 + 15 = 21
- Fill in dp[2][6] = dp[1][6] + dp[2][5] = 7 + 21 = 28
- Final dp grid = [[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]]
- Return dp[2][6] = 28, which is the number of unique paths to the bottom-right corner.
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the grid and the number of unique paths to each cell as calculated by the dynamic programming algorithm.
Key visualization elements:
- current cell
- path count
- direction of movement
Implementation Notes
This problem is a classic dynamic programming problem that introduces the concept of calculating combinations. It can be solved using a 2D grid approach, a space-optimized 1D approach, or even using combinatorial mathematics.