Unique Paths Problem Solution

Unique Paths Problem: 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.

Input: m = 3, n = 7
Output: 28

Unique Paths Problem Solution

Problem Solution In Python

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

Problem Solution In Java

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0;i < m;i++) 
            for(int j = 0;j < n;j++) 
                dp[i][j] = i == 0 || j == 0 ? 1 : dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }
}

Problem Solution In C++

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            dp[i][0]=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];
    }
};

Problem Solution In C

int solve(int **count, int m, int n, int row, int col) {
    if (row == m || col == n) {
        return 0;
    }
    
    if (count[row][col] != -1) {
        return count[row][col];
    }
    
    if (row == m - 1 && col == n - 1) {
        count[row][col] = 1;
        return 1;
    }
    
    int down = solve(count, m, n, row + 1, col);
    int right = solve(count, m, n, row, col + 1);
    int uniquePaths = down + right;
    count[row][col] = uniquePaths;
    return uniquePaths;
}

int uniquePaths(int m, int n){
    int **count = malloc(m * sizeof(int *));
    for (int i = 0; i < m; ++i) {
        count[i] = malloc(n * sizeof(int));
        memset(count[i], -1, n * sizeof(int));
    }

    int uniquePaths = solve(count, m, n, 0, 0);

    for (int i = 0; i < m; ++i) {
        free(count[i]);
    }
    free(count);
    return uniquePaths;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment