Problem Statement
Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10^9.
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:
1. Right -> Right -> Right -> Right -> Right -> Right -> Down -> Down
2. Right -> Right -> Right -> Right -> Right -> Down -> Right -> Down
...
28. Down -> Down -> Right -> Right -> Right -> Right -> Right -> Right
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
2. Down -> Right
3. Down -> Down -> Right
Constraints
- 1 <= m, n <= 100
- The answer will be less than or equal to 2 * 10^9
Problem Breakdown
To solve this problem, we need to:
- This problem can be solved using dynamic programming.
- The number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the cell to its left.
- The base case is that there is only one way to reach any cell in the first row or first column (by moving only right or only down, respectively).
- The problem can also be solved using combinatorics, as it's equivalent to choosing which steps should be 'down' steps out of a total of m+n-2 steps.
- The formula for the combinatorial solution is C(m+n-2, m-1) or C(m+n-2, n-1), which is (m+n-2)! / ((m-1)! * (n-1)!).
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10^9.
Examples
Example 1:
From the top-left corner, there are a total of 28 ways to reach the bottom-right corner: 1. Right -> Right -> Right -> Right -> Right -> Right -> Down -> Down 2. Right -> Right -> Right -> Right -> Right -> Down -> Right -> Down ... 28. Down -> Down -> Right -> Right -> Right -> Right -> Right -> Right
Example 2:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down 2. Down -> Right 3. Down -> Down -> Right
Problem Breakdown
Constraints:
- 1 <= m, n <= 100
- The answer will be less than or equal to 2 * 10^9
Key Insights:
This problem can be solved using dynamic programming.
The number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the cell to its left.
The base case is that there is only one way to reach any cell in the first row or first column (by moving only right or only down, respectively).
The problem can also be solved using combinatorics, as it's equivalent to choosing which steps should be 'down' steps out of a total of m+n-2 steps.
The formula for the combinatorial solution is C(m+n-2, m-1) or C(m+n-2, n-1), which is (m+n-2)! / ((m-1)! * (n-1)!).
Real-World Application
This problem has several practical applications:
Robot Path Planning
Planning optimal paths for robots in grid-based environments, such as warehouses or factories.
Network Routing
Calculating the number of possible routes in network topologies with restricted movement directions.
City Navigation
Determining the number of possible routes in a city with a grid-like street layout where only eastward and southward movements are allowed.