CareerCup

Check this
techieme.in/techieme/dynamic-programming-distinct-paths-between-two-points/

Catalan number

What are the allowed movements?
down and right?
Along the lines?

If only down and right are allowed the solution is simple by using combinatorics, in a [m][n] matrix the answer is C(m+n, m).

You can also use backtracking to find the paths, just keep adding one until all paths are exhausted.

If we assume the robot can only move down and to its right.

/* compute the number of move of a robot
 * from (0,0) to (x,y)
 */
unsigned long long robot_table[1024][1024];
unsigned long long robot_move (int x, int y)
{
    if (x == 0) {
        return (1);
    }
    if (y == 0) {
        return (1);
    }
    if (robot_table[x][y]) {
        return (robot_table[x][y]);
    }
    robot_table[x][y] = robot_move(x-1, y) + robot_move(x, y-1);
    return (robot_table[x][y]);
}

int ii = 4;
int jj = 4;

int max_path(int i, int j){

int count=0;
if(i==(ii-1) && j == (jj-1)){
return 1;
}
if(i < ii){
count += max_path(i+1,j);
}
if(j < jj){
count += max_path(i,j+1);
}
return count;

}

int _tmain(int argc, _TCHAR* argv[])
{
printf("Number of Paths: %d", max_paths(0,0));
return 0;
}

Ill-posed problem. Is backtracking allowed or not?

if you can move down and right then you hv 2 possiblity only.check the below code

int no_of_path(int n1,int n2,int i,int j)
{
	if(i==n1 || j==n2)
		return 1;
	if(i==n1-1 && j==n2-1)
		return 2;
    return (no_of_path(n1,n2,i+1,j)+no_of_path(n1,n2,i,j+1));
}

LCS