Algorithm
Problem Name: 62. Unique Paths
Problem Link: https://leetcode.com/problems/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 * 109.
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: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down
Constraints:
1 <= m, n <= 100
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int uniquePaths(int m, int n) {
int path[100][100];
int i, j;
if (!m || !n) return 0;
for (i = 0; i < m; i ++) {
for (j = 0; j < n; j ++) {
if (i == 0 || j == 0) {
path[i][j] = 1;
} else {
path[i][j] = path[i][j - 1] + path[i - 1][j];
}
}
}
return path[m - 1][n - 1];
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>>dp(m, vector<int>(n));
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int i = 0; i < n; i++) dp[0][i] = 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];
}
};
class Solution {
public:
int uniquePaths(int m, int n) {
vector < vector<int>>dp(m + 1, vector<int>(n + 1));
dp[1][1] = 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][n];
}
};
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int>dp(n);
dp[0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int[] arr : dp) {
Arrays.fill(arr, 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];
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const uniquePaths = function(m, n) {
if(m === 0 || n === 0) return 0
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(1))
dp[0][1] = dp[1][0] = 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]
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * m for _ in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(m):
if i - 1 >= 0:
dp[i][j] += dp[i - 1][j]
if j - 1 >= 0:
dp[i][j] += dp[i][j - 1]
return dp[-1][-1]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _062_UniquePaths
{
public int UniquePaths(int m, int n)
{
var rest = Math.Min(m - 1, n - 1);
if (rest == 0) { return 1; }
if (rest == 1) { return m + n - 2; }
long result = 1;
int temp = m + n - 2, i = rest;
while (i-- > 0)
{
result *= temp--;
}
while (rest > 1)
{
result /= rest--;
}
return (int)result;
}
}
}
Input
Output