Problem Statement:
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 * 109.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: m = 3, n = 7
Output: 28
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:
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
Constraints
- 1 <= m, n <= 100
Approach:
- DP Definition: Let
dp[i][j]represent the number of unique paths to reach cell(i,j) - Bases cases are like this:
- First row → Only one way (all moves right).
- First column → Only one way (all moves down).
- Transition: To reach (i,j), you can come from:
- Above:
(i-1, j) - Left:
(i, j-1)
- Above:
- Final result is at
bottom-right cell → dp[m-1][n-1].
Time & Space Complexity:
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Dry Run
Input: m = 3, n = 3
Initial dp matrix (all -1):
[[-1, -1, -1],
[-1, -1, -1],
[-1, -1, -1]]
Step 1: Fill first column with 1
[[1, -1, -1],
[1, -1, -1],
[1, -1, -1]]
Step 2: Fill first row with 1
[[1, 1, 1],
[1, -1, -1],
[1, -1, -1]]
Step 3: Fill remaining cells using dp[i][j] = dp[i-1][j] + dp[i][j-1]
i = 1, j = 1:
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
[[1, 1, 1],
[1, 2, -1],
[1, -1, -1]]
i = 1, j = 2:
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
[[1, 1, 1],
[1, 2, 3],
[1, -1, -1]]
i = 2, j = 1:
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
[[1, 1, 1],
[1, 2, 3],
[1, 3, -1]]
i = 2, j = 2:
dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
[[1, 1, 1],
[1, 2, 3],
[1, 3, 6]]
Final dp matrix:
[[1, 1, 1],
[1, 2, 3],
[1, 3, 6]]
Answer = dp[m-1][n-1] = dp[2][2] = 6
Output: 6
var uniquePaths = function(m, n) {
let dp = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) dp[i][0] = 1;
for (let j = 0; j < n; j++) dp[0][j] = 1;
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
};
def uniquePaths(m, n):
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
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];
}
}
#include <vector.h>
using namespace std;
class Solution {
public:
int uniquePaths(int m, int n) {
vector> dp(m, vector(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
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];
}
};
#include <stdio.h>
int uniquePaths(int m, int n) {
int dp[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
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];
}
public class Solution {
public int UniquePaths(int m, int n) {
int[,] dp = new int[m, n];
for (int i = 0; i < m; i++) dp[i, 0] = 1;
for (int j = 0; j < n; j++) dp[0, j] = 1;
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];
}
}
