Simple C++ version using Math


  • 25
    D
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            if(m <=0 || n <= 0) return 0;
            long long res = 1;
            for(int i = n; i < m+n-1 ; i++){
                res = res * i / (i- n + 1);
            }
            return (int)res;
        }
    };
    

    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. Then different choice number would be:


    UniqueStepNum = choose (m-1) from (m+n-2) = choose (n-1) from (m+n-2)


    = (m+n-2)! / [(m-1)! * (n-1)!]


    = ( (m+n-2) / (m-1) ) * ( (m+n-3) / (m-2) ) * ... * (n / 1)


  • 0
    Z

    The mathematical solution makes perfect sense, but I have a question about the code: how do we make sure that res * i / (i- n + 1) is an integer at every iteration? If the actual value of res * i / (i- n + 1) has a decimal point, the value of res may not be correct at the end.


  • 5
    G

    Here is the proof that res is always an integer.

    When i=k (n<=k)

    enter image description here

    We know Binomial coefficient is always an integer, then res is always an integer.

    To prove Binomial coefficient is integer, search other articles, for example here.


  • 0
    G

    See my answer.


  • 0
    Z

    I am aware of that res is equal to the binomial coefficient, which is always an integer. My question is about the intermediate value of res. Specifically, how do we know whether AT EACH ITERATION "res * i" is divisible by "(i- n + 1)"?


  • 0
    G

    In the for loop, doesn't i increase from n to m+n-1? In my proof, I show that whenever i>=n (the intermediate steps), res equals the formula, res equals binominal coefficient. The res in my formula refers to the res in the left hand side in the code.


  • 0
    Z

    I see now. Sorry for misunderstanding your proof. Thank you.


  • 0
    This post is deleted!

  • 1

    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 {
    public:
        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);
        }
    };

  • 0
    T

    @deartonym thanks for sharing, yours is simpler than my idea:

    what I am doing is also the mathematics way:

    // Math: (m+n-2)!/ (m-1)!(n-1)!
    
    
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            double number = 1, denominator = 1;
            if( m == 0 || n == 0) {return 0;}
            if( m == 1 || n == 1) {return 1;}
            
            if(m >= n)  // divide by (m-1)! first
            {
                for(int i = m+n-2; i > m-1; --i)
                    number *= i;
                for(int i = 1; i <= n-1; ++i)
                    denominator *= i;
                return (number/denominator);
            }
            else  // divide by (n-1)! first
            {
                for(int i = m+n-2; i > n-1; --i)
                    number *= i;
                for(int i = 1; i <= m-1; ++i)
                    denominator *= i;
                return (number/denominator);
            }
          
        }
    }; 
    

Log in to reply
 

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