C++ math method.

  • 0

    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 {
        int uniquePaths(int m, int n) {
            long cnt=1;
            if (m>n) swap(m,n);//to have a shorter 'for' loop
            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.