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
Constraints
1 <= m, n <= 100
Dynamic Programming (2D Array)
Approach
We can use a 2D array `dp` of size `m x n` where `dp[i][j]` represents the number of unique paths to reach cell `(i, j)`. Since the robot can only move down or right, it can reach cell `(i, j)` from either `(i-1, j)` (top) or `(i, j-1)` (left). Therefore, `dp[i][j] = dp[i-1][j] + dp[i][j-1]`. We initialize the first row and first column to 1, because there is only one way to reach any cell in the first row (keep going right) and the first column (keep going down).
Complexity Analysis
Time complexity is O(m * n) as we calculate the number of paths for each cell once. Space complexity is O(m * n) to store the 2D array. (Space can be optimized to O(n) by only keeping the previous row).
class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; // Fill first column with 1s for (int i = 0; i < m; i++) { dp[i][0] = 1; } // Fill first row with 1s for (int j = 0; j < n; j++) { dp[0][j] = 1; } // Calculate paths for remaining cells for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; }}