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.
