CareerCup

In a grid?

recursive solution

public static int dofindNumOfWays(int [] [] matrix, int i ,int j,int value){
		if (i>=matrix.length||j>=matrix[0].length){
			return 0;
		}else if (matrix[i][j]==value){
			return 1;
		}else{
			int right = 0;
			int down = 0;
			int diagno = 0;
			right = dofindNumOfWays(matrix,i,j+1,value);
			diagno = dofindNumOfWays(matrix,i+1,j+1,value);
			down  = dofindNumOfWays(matrix,i+1,j,value);             
			return right + down + diagno ;
		}

}

Grid can be viewed as strongly connected graph, so u can use djiktra Algorithm

dp solution

public static int findWaysDP (int [] []matrix , int x, int y){
		int row = matrix.length;
		int col = matrix[0].length;
		int [] [] dp = new int [row][col];
		dp [0][0] = 1;	
		for (int i = 0 ; i<row ;++i){
			for (int j = 0 ; j <col ;++j){
				// horizon
				if (j+1<col){
					dp [i][j+1] += dp[i][j];
				}
				//diagno 
				
				if (j+1<col &&i+1<row){
					dp [i+1][j+1] += dp[i][j];
				}
				
				
				//down
				if (i+1<row){
					dp [i+1][j]+= dp[i][j];
				}
				
			}
		}
		
		
		return dp [x][y];

}

Use wave algorithm

How about doing an A* search? The nodes (grid points in this case) are expanded based on the function f(x) = g(x) + h(x), where g(x) = path code till now to arrive at node (a,b), where 0<=a<x and 0<=b<y, and h(x) = the heuristic function which describes the estimated cost to get to (i,j) from (a,b). If the heuristic chosen is admissible and monotonic, the A* will give you the optimal path. We can use DP to compute h(a,b) and f(a,b).