Leetcode Unique Paths problem solution

In this Leetcode Unique Paths problem solution A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

Leetcode Unique Paths 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]

Unique Paths 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;
}

Leetcode Unique Paths problem solution in Python.

Unique Paths problem solution in Java.

Problem solution in C++.

Problem solution in C.

Leave a Reply