long numberOfPaths(int m, int n)
{
// code here
return NumberOfPaths(0,0, m-1, n-1, new long[m][n]);
}
private long NumberOfPaths(int cx,int xy,int tx, int ty, long[][] arr){
if(cx == tx && xy == ty){
return 1;
}
if(cx > tx || xy > ty){
return 0;
}
if(arr[cx][xy] != 0){
return arr[cx][xy];
}
long count = 0;
count += NumberOfPaths(cx+1,xy,tx,ty, arr);
count += NumberOfPaths(cx,xy+1,tx,ty, arr);
arr[cx][xy] = count;
return count;
}
}