My AC solution using formula


  • 116
    D

    Binomial coefficient:

    class Solution {
        public:
            int uniquePaths(int m, int n) {
                int N = n + m - 2;// how much steps we need to do
                int k = m - 1; // number of steps that need to go down
                double res = 1;
                // here we calculate the total possible path number 
                // Combination(N, k) = n! / (k!(n - k)!)
                // reduce the numerator and denominator and get
                // C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
                for (int i = 1; i <= k; i++)
                    res = res * (N - k + i) / i;
                return (int)res;
            }
        };
    

    First of all you should understand that we need to do n + m - 2 movements : m - 1 down, n - 1 right, because we start from cell (1, 1).

    Secondly, the path it is the sequence of movements( go down / go right),
    therefore we can say that two paths are different
    when there is i-th (1 .. m + n - 2) movement in path1 differ i-th movement in path2.

    So, how we can build paths.
    Let's choose (n - 1) movements(number of steps to the right) from (m + n - 2),
    and rest (m - 1) is (number of steps down).

    I think now it is obvious that count of different paths are all combinations (n - 1) movements from (m + n-2).


  • 0
    S

    Thanks for your post. Can you elaborate the formula by some words? Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    R

    Please elaborate how did u get this formula???


  • 0
    D

    I added the explanation, I think it will help to understand better


  • 6
    M
    return round(res); 
    

    would be better ^_^


  • 1
    K

    I think double is not necessary. No decimal fraction will occur in your algorithm. I prefer long and use k = min(m-1,n-1) to reduce time consumption and possibility of overflow.


  • 5
    M

    Java version

    public int uniquePaths(int m, int n) {
        double value = 1;
        for (int i = 1; i <= n - 1; i++) {
            value *= ((double) (m + i - 1) / (double) i);
        }
        return (int) Math.round(value);
    }

  • 0
    S

    yes, agree about this


  • 0
    M
    This post is deleted!

  • 1
    S

    killerwyatt, what was the reason that u said ' No decimal fraction will occur' ?


  • 2
    H

    Python version:

    def uniquePaths(self, m, n):
        return reduce(lambda res, i: res * (n - 1 + i) / i, range(1, m), 1)

  • 0
    C

    good Job!I like it !


  • 8
    D

    https://www.youtube.com/watch?v=M8BYckxI8_U
    Watch the video for those who still do not understand the solution.


  • 0
    P

    What does "AC" means? is it design technique? or means just "accepted"?


  • 1
    A

    I think the if the code " int k = m - 1;" change to "int k = min(m - 1,n-1)"will be better than now.


  • 0
    Y

    That's Catlan number~!


  • 2

    the calculation res = res * (N - k + i) / i; may cause losing precision, and as the number gets larger, the error may increase, how can you guarantee that (int)res is the exact result?


  • 0
    A

    @james.wang.cccgmail.com James, I think this formula {m+1 \choose n+1} = {m \choose n} \cdot \frac{m+1} \frac{n+1} answers your question. Note that {m+1 \choose n+1} and {m \choose n} are both integers. Basically, this algorithm is calculating from {m \choose n} to {m+1 \choose n+1}.


  • 0
    M

    very clever!


  • 0
    W

    @d40a just an optimization
    k=min(m,n) - 1;


Log in to reply
 

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