The more efficient C++ version using permutations

  • 2

    As deartonym said in here, the total step number should be m+n-2. This means that we have to move down for m-1 steps and move right n-1 steps to reach the definition.

    If you studied permutations, you will know the key is C(m+n-2, m-1), or it can be written as C(m+n-2, n-1), these two expressions are equal.

    In order to facilitate the calculation, we should choose min(m-1, n-1) as the second item. So the follow is the more efficient code:

    class Solution {
        int uniquePaths(int m, int n) {
            int A = m + n - 2, B = std::min(m - 1, n - 1);
            long long result = 1;
            for (int i = 1; i <= B; ++i)
                result = result * A-- / i;
            return static_cast<int>(result);

Log in to reply

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