One math one DP solution, both accepted as best in C


  • 0
    //AC - 0ms;
    int uniquePaths(int m, int n)
    {
        if(m > n) return uniquePaths(n, m);
        m--, n--;
        long long denominator = 1;
        long long member = 1;
        while(m > 0)
        {
            member *= m + n;
            denominator *= m;
            m--;
        }
        return member / denominator;
    }
    

    //AC - 0ms;
    int uniquePaths(int m, int n)
    {
        if(m > n) return uniquePaths(n, m);
        int *arr = (int*)malloc(sizeof(int)*m);
        for(int i = 0; i < m; i++)
            arr[i] = 1;
        for(int i = 1; i < n; i++)
            for(int j = 1; j < m; j++)
                arr[j] += arr[j-1];
        return arr[m-1];
    }

  • 0
    G
    class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m == 0 or n == 0:
            return 0
        if m == 1 or n == 1:
            return 1
    
        board = [[1] * m for _ in xrange(n)]
        board[0][1] = 1
        board[1][0] = 1
        
        for i in xrange(1, n):
            for j in xrange(1, m):
                
                board[i][j] = board[i - 1][j] + board[i][j - 1]
        return board[n - 1][m - 1]

Log in to reply
 

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