# Leetcode Unique Paths problem solution

Apr 14, 2023

In the Leetcode Unique Paths problem solution 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

## Solution in C Programming

``````int uniquePaths_help(int **dp, int x, int y, int m, int n) {
if(x+1 >= m || y+1 >= n) return 1;
/* Search count from table */
if(dp[x][y]) return dp[x][y];

int k = 0;

// Go right
dp[x+1][y] = uniquePaths_help(dp, x+1, y, m, n);
k += dp[x+1][y];

// Go down
dp[x][y+1] = uniquePaths_help(dp, x, y+1, m, n);
k += dp[x][y+1];

return k;
}

int uniquePaths(int m, int n) {
/* start from (0, 0) to (m-1, n-1), only move right or down */
int **dp = malloc(m*sizeof(int *));
for(int i=0;i<m;i++) {
dp[i] = malloc(n*sizeof(int));
memset(dp[i], 0, n*sizeof(int));
}

dp[0][0] = uniquePaths_help(dp, 0, 0, m, n);

// for(int i=0;i<m;i++) {
//     for(int j=0;j<n;j++) {
//         printf("%4d,", dp[i][j]);
//     }
//     printf("\n");
// }

return dp[0][0];
}``````

## Solution in C++ Programming

``````class Solution {
public:
int uniquePaths(int m, int n) {

vector<vector<int>> dp(m, vector<int>(n,0));

for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 && j==0){
dp[0][0] = 1;
}
else if(i-1<0 && j-1>=0){
dp[i][j] = dp[i][j-1];
}
else if(i-1>=0 && j-1<0){
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
``````

## Solution in Java Programming

``````class Solution
{
public int uniquePaths(int m, int n)
{
int[] ans = new int[m];
Arrays.fill(ans, 1);

for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
ans[j] = ans[j] + ans[j-1];
}
}
return ans[m-1];
}
}``````

## Solution in Python Programming

``````class Solution:
def uniquePaths(self, m, n):
# the base case is that if robot just go in the first column or the first row, there will be only one possible path for each, since the robot can only go down or right.
# that's why we intialize all values as 1, to represent the first row
record = [1]*n
# and we start from index 1 for row and column for the same sense.
for i in range(1,m):
for j in range(1,n):
record[j] = record[j-1]+record[j]
return record[-1]``````

## Solution in C# Programming

``````public class Solution {
public int UniquePaths(int m, int n) {
int[,] table = new int[m,n];

for(int i = m-1; i >= 0; i--){
for(int j = n -1; j >= 0; j--){
if(i == m -1 || j == n -1){
table[i, j] = 1;
}
else{
table[i,j] = table[i+1, j] + table[i, j+1];
}
}
}

return table[0,0];
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.