C++ solution with combinatorics

programming
Tags: #<Tag:0x00007f2427322060>

#1

int Solution::uniquePaths(int n, int m) {

int l = n+m-2;
int j = 1;
long long ans = 1;// compute l C s = l! /(s! * (l-s)!);
for(int s = n; s <=l; s++){
    ans *= s;
    ans /=j;
    j++;
}

return ans;

}


#2

Can you please explain how is this working?


#3

Yea sure.(But not sure what you want me to explain( the code ?or how is this a solution?)
Let me encourage you to think in direction. Here in N X M grid , what is the path length by which you can go from (1,1) to (N,M) . Count the total cells e.g (5 X 4)(Think before you read below)

1,1->1,2->1,3->1,4->2,4-> 3,4->4,4->5,4 (one such a path); What is the total number of edges here 7. (5+4-2)
Hence you need n+m-2 edges or(options available)

Another way to think.
what is the restriction over path

  1. At every choice(only column/row) should increase
  2. row can not go beyond N
  3. column can not go beyond M
    To go from 1 to N you need N-1 edges and similarly M-1 edges from 1 to M.
    From this also you can conclude you have (N-1 + M-1) = N+M-2 edge choices.

Second gives you more intuitive way.
Can you think of solution now?

Ok. Imagine you have been given a sequence c1c1c1r1r1r1r1 where each choice depicts either row increment or column increment. How many combinations can you form now? Simple?

Basically chose any 4 slots out of 7 for putting the element r1.
7C4 => (m+n-2)Cn-1 (isn’t it).