# My AC solution using formula

• 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).

• 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

• Please elaborate how did u get this formula???

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

• return round(res);


would be better ^_^

• 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.

• 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);
}

• This post is deleted!

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

• Python version:

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

• good Job！I like it !

Watch the video for those who still do not understand the solution.

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

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

• That's Catlan number~!

• 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?

• @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}.

• very clever!

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

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