CareerCup

1. It is a typic combination problem.
For (0,0) to (i, j) is C(i+j, i) = (i+j)!/i!/j!
2. If there are blocks on the way, then, dynamic programming is needed for performance.
It is just a reverse way to calculate f(i, j) = f(i - 1, j) + f(i, j-1) with special cases some f(x, y) = 0.

Hey, these are standard DP problems. Identify each subproblem as the number of ways you can reach the location (k,l) starting from (0,0), then it can be calculated as the sum of the number of ways reaching (k-1,l) and (k,l-1), and you can use either bottom-up approach or a top-down memorization approach to solve it. When there are blocks, you just need to put additional checks inside the code before you sum them. These questions are given in LeetCode Online Judge that not only allows you to type in your (Java or C++) code in a panel, but also checks if it is correct and if its performance is not exponential.

@vqeek what u have given is a way....in question they ask for how many ways are possible...we can go right down right down....zigzag path..

Please let me know if the following dynamic programming approach is correct:

t[0][0]=0; //target location i.e., bottom-right corner
for(i=n-2;i>=0;i--)
t[n-1][i]=1;//there is only one way for the last row blocks since moving up is prohibited and moving down will lead us off the grid
for(i=n-2;i>=0;i--)
t[i][n-2]=1; //there is only one way for the last column blocks since moving right leads us off the grid and we are not allowed to go to the left
j=n-3;i=n-3;
while(i>=0 && j>=0)
{
if(t[i+1][j]>=t[i][j+1]) //we are looking for the maximum number of ways hence >=
t[i][j]=t[i+1][j]+1;
else
t[i][j]=t[i][j+1]+1;
}
return t[0][0];

class Program
    {
        static void Main(string[] args)
        {
            GridPath p = new GridPath(1,1);
            p = new GridPath(2, 2);
            p = new GridPath(3, 3);
            p = new GridPath(4, 4);
            p = new GridPath(5, 5);
            p = new GridPath(6, 6);
            p = new GridPath(7, 7);
            p = new GridPath(8, 8);
            p = new GridPath(9, 9);
            Console.ReadKey();
        }

        public class GridPath
        {
            static int possibilitiesFound;
            static int N;  //width
            static int M;  //height
            public GridPath(int width, int height)
            {
                possibilitiesFound = 0;
                N = width;
                M = height;
                StepPath(1, 1);
                Console.WriteLine(possibilitiesFound);
            }
            private static void StepPath(int i, int j)
            {
                // check for blocks and return if found, for instance: if ((i == 2) && (j == 2)) return;

                if (j < M) { StepPath(i, j + 1); }
                if(i < N) { StepPath(i + 1, j); }
                if ((j == M) && (i == N)) { possibilitiesFound++; }
            }
        }
    }

int getways(int N, int M, int r, int c) { // target is cell[r,c]
		int[] store = new int[N];
		if(c==0) 
			return 1;
		store[0] = 1;
		
		for(int i=0; i<N; i++)
			for(int j=1; j<M; j++) {
				store[j] += store[j-1];
				if(i==r && j==c)
					return store[j];
			}
}

Standard Backtracking Problem

Cant we solve this problem straightaway. I mean if you start with (0,0) and if you have to move to any arbitrary location (i,j) while moving either to the right or bottom in one step then.
Consider the location (3,5) then to reach (3,5) from (0,0) the number of steps are 8 that is 3+5 as you either increase the row number by one or column number by one. So to reach the location (i,j) the number of steps involved are (i+j).Here the shortest path does not matter as you cannot move diagonally .You can only move either right or down. Correct me if i am wrong

static int getWays(int toX, int toY)
        {
            if (toX == 0 || toY == 0)
                return 1;
            else
                return getWays(toX - 1, toY) + getWays(toX, toY - 1);
        }