Back to DSA
Unique Paths
mediumA traveler starts in the upper-left cell of an m-by-n grid and wants to reach the lower-right cell. Movement is restricted to going one cell right or one cell down at each step. Count how many distinct routes exist from start to finish.
Examples
Example 1:
Input:
m = 4, n = 3Output:
10Explanation: There are 10 distinct routes from the top-left to the bottom-right of a 4x3 grid.
Example 2:
Input:
m = 2, n = 5Output:
5Explanation: In a 2x5 grid, there are 5 distinct routes.
Hints
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
java.util.Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}Time complexity
O(m * n)Space complexity
O(n)