Leetcode Unique Paths Problem Solution

In this 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.

Problem solution in Python.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for i in range(m)] if i == 0 else [1 if i == 0 else 0 for i in range(m)] for i in range(n)]
        
        for i in range(1,n):
            for j in range(1,m):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
        return dp[n-1][m-1]

Problem solution in Java.

public int uniquePaths(int m, int n) {
    int[] first = new int[m];
    int[] second = new int[m];
    for (int i = 0; i< m; i++) {
        first[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j == 0) {second[j] = 1;}
            else {
                second[j] = second[j-1] + first[j];
            }
        }
        first = second;
    }
    return first[m-1];
}

Problem solution in C++.

class Solution {
public:
    int cp(int m, int n,int i, int j,vector<vector<int>>&dp){
        if(i==(m-1)&& j==(n-1))return 1;
        if(i>=m||j>=n)return 0;
        if(dp[i][j]!=-1)return dp[i][j];
        else return dp[i][j]=cp(m,n,i+1,j,dp)+ cp(m,n,i,j+1,dp);
    }
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m,vector<int>(n,-1));
        
        return cp(m,n,0,0,dp);
        
        
    }
};

Problem solution in C.

int uniquePaths(int n, int m){
    int a[n][m];
    int i,j;
    a[0][0]=1;
    for(i=1;i<n;i++)
        a[i][0]=1;
    for(j=1;j<m;j++)
        a[0][j]=1;
    for(i=1;i<n;i++)
        for(j=1;j<m;j++)
            a[i][j]=a[i-1][j]+a[i][j-1];
    return a[n-1][m-1];
}