C++ math method.


  • 0
    A

    There are (m+n-2) steps in each path, (m-1) of them are downwards and (n-1) are rightwards.

    Thus the answer is the combination C(m+n-2)(m-1), or C(m+n-2)(n-1).

    Use long int to avoid overflow.

    class Solution {
    public:
        int uniquePaths(int m, int n) {
            long cnt=1;
            if (m>n) swap(m,n);//to have a shorter 'for' loop
            n--;
            for (int i=1;i<m;i++) cnt=cnt*(n+i)/i;
            return cnt;
        }
    };

Log in to reply
 

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