Unique Paths
A robot on an m x n grid starts at top-left and can only move right or down. How many unique paths exist to the bottom-right?
Example:
3 7
28
- The grid size is determined by the input values, with m=3 rows and n=7 columns.
- To reach the bottom-right corner, the robot must make m−1=2 moves down and n−1=6 moves right, for a total of m+n−2=8 moves.
- The number of unique paths is equivalent to choosing m−1=2 moves down out of the total 8 moves, which can be calculated using the binomial coefficient: (28​)=2!(8−2)!8!​=28⋅7​=28.
- The final output is the result of this calculation, which represents the total number of unique paths to the bottom-right corner.
Constraints:
- 1 <= m, n <= 100
Background Knowledge
The "Unique Paths" problem is a classic example of a combinatorial problem that can be solved using dynamic programming. To understand this problem, it's essential to have a basic grasp of combinatorics, which is the study of counting and arranging objects in various ways. In this case, we're counting the number of unique paths a robot can take to reach the bottom-right corner of a grid. The robot can only move right or down, which means that each path is a sequence of right and down moves.
The key concept here is that the number of unique paths to a cell is the sum of the number of unique paths to the cell above it and the cell to its left. This is because the robot can only reach a cell by moving down from the cell above or right from the cell to its left. This idea is the foundation of the dynamic programming approach, which involves breaking down a problem into smaller sub-problems, solving each sub-problem only once, and storing the solutions to sub-problems to avoid redundant computation.
To solve this problem, you should also be familiar with grid traversal and memoization, which are common techniques used in dynamic programming. Grid traversal involves iterating over a grid and performing operations on each cell, while memoization involves storing the results of expensive function calls so that they can be reused instead of recomputed.
Algorithm/Approach
The general approach to solving this type of problem is to use a bottom-up dynamic programming approach. This involves creating a 2D array, dp, where dp[i][j] represents the number of unique paths to the cell at position (i, j). The algorithm starts by initializing the first row and column of the dp array, since there is only one way to reach each cell in the first row (by always moving right) and each cell in the first column (by always moving down).
Step-by-Step Strategy
To implement the solution, follow these steps:
- Create a 2D array, dp, with dimensions m x n, where m is the number of rows and n is the number of columns.
- Initialize the first row and column of the dp array, since there is only one way to reach each cell in the first row and each cell in the first column.
- Iterate over the remaining cells in the dp array, and for each cell, calculate the number of unique paths to that cell by adding the number of unique paths to the cell above it and the cell to its left.
- The final answer will be stored in the bottom-right cell of the dp array, dp[m-1][n-1].
Common Pitfalls
When implementing the solution, watch out for the following common pitfalls:
- Forgetting to initialize the first row and column of the dp array correctly.
- Using the wrong indices when accessing the dp array, since array indices in most programming languages are 0-based.
- Not handling edge cases, such as when m or n is 1.
Time & Space Complexity
The time complexity of the solution is O(mn), since we need to iterate over each cell in the dp array once. The space complexity is also O(mn), since we need to store the dp array, which has dimensions m x n. Note that the space complexity can be optimized to O(n) by only keeping track of the previous row, since each cell only depends on the cell above it and the cell to its left.