which is nothing but C(2n-2,n-1) Catalan Number ???? i don't think so?? for a n*n grid answer is 2n!/n!n! but catalan number gives ans as 2n!/(n+1)!n!
On Thu, Mar 3, 2011 at 8:12 PM, bittu <[email protected]> wrote: > both DP & Catalan Number solve this > > 1st Approach Catalan Number > > (For clarity, we will solve this part assuming an X*Y Matrix) > Each path has (X-1)+(Y-1) steps. Imagine the following paths: > > X X Y Y X (move right -> right -> down -> down -> right) > X Y X Y X (move right -> down -> right -> down -> right) > ...& so on > > Each path can be fully represented by the moves at which we move > right. That is, if I were to ask you which path you took, you could > simply say “I moved right on step 3 and 4.” > Since you must always move right X-1 times, and you have X-1 + Y-1 > total steps, you have to pick X-1 times to move right out of X-1+Y-1 > choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose > X-1): > > (X-1 + Y-1)! / ((X-1)! * (Y-1)!)..Hope This Equation Clear to Every1 > > which is nothing but C(2n-2,n-1) Catalan Number > > > 2nd Approach > > DP(Always Best) > > A robot can take path (N,M) from either (N-1,M) or (N,M-1) > if N and M is 0, its the beginning so return 0. > if N or M is 0, we can get there in 1 path. > > We call paths(N,M) with s[][] initialized to -1. > > int paths(int i,int j) > { > if(!(i||j)) //means we either can go down or right path as only 1 is > zero > return 1; > > if((i&&j))/// no path exist if both are zero > return 0; > > if(s[i][j] != -1) > return s[i][j]; > > s[i][j] = paths(i-1,j) + paths(i,j-1); > > return s[i][j]; > } > > > I thinks We All Have Done With Thread. Still if Some has Doubt or > Found Anything Wrong Please Let me Know > > > Thanks & Regards > Shashank Mani >>"The Best Way to Escape From The Problem is Solve It" > Computer Science & Engineering > Birla Institute of Technology,Mesra > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
