Java different solutions (math, dp(O(m*n), O(n) space)).


  • 2
    C
    import static java.lang.Math.toIntExact;
    public class Solution {
    // math 
    public int uniquePaths1(int m, int n) {
        m--; n--;
        long ret=1;
        for (int i=1; i<=Math.min(m, n); i++) {
            ret = ret * (m+n+1-i)/i; //take care here 
        }
        return toIntExact(ret);
    }   
    
    // O(n*m) space, dp
    public int uniquePaths2(int m, int n) {
        int dp[][] = new int[m][n];
        for (int i=0; i<m; i++)
            dp[i][0] = 1;
        for (int j=0; j<n; j++)
            dp[0][j] = 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];
    }
    
    // O(n) space, dp
    public int uniquePaths(int m, int n) {
        int []dp = new int[n];
        for (int j=0; j<n; j++)
            dp[j] = 1;
        for (int i=1; i<m; i++) 
            for (int j=1; j<n; j++)
                dp[j] += dp[j-1];
         return dp[n-1];       
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.