CareerCup

int[,] m = new m[3,3]
FindMinimumPath(m, 0, 0, 3, 3)

public static int FindMinimumPath(int[,] m, int x, int y, int tx, int ty)
{
int path1 = int.MaxValue;
int path2 = int.MaxValue;
int path3 = int.MaxValue;

if(x+1 == tx && y+1 == ty)
return m[x,y];

if(x+1 < tx)
path1 = FindMinimumPath(m, x+1, y, tx, ty);

if(y+1 < ty)
path2 = FindMinimumPath(m,x,y+1, tx,ty);

if(x+1 < tx & y+1 < ty)
path3 = FindMinimumPath(m, x+1, y+1, tx, ty);

return m[x,y] + Math.Min(path1, Math.Min(path2, path3));

}

you can solve this problem by recursion.

I have implemented it using Iterative Dynamic Programming.

public class Main {

	public static void main(String[] args) {
		int[][] costMatrix = { {4, 5, 6},
                			       {1, 2, 3},
                			       {0, 1, 2} };
		
		System.out.println("Minimum cost to traverse = "+minCost(costMatrix));

	}
	
	public static int minCost(int[][] costMatrix){
		int[][] mat = new int[costMatrix.length][costMatrix[0].length];
		mat[mat.length-1][mat[0].length-1] = 
				costMatrix[mat.length-1][mat[0].length-1];
		for(int j=mat[0].length-2; j>=0; j--){
			int lastRow = mat.length-1;
			mat[lastRow][j] = mat[lastRow][j+1] + costMatrix[lastRow][j];
		}
		for(int i=mat.length-2; i>=0; i--){
			int lastCol = mat[0].length-1;
			mat[i][lastCol] = mat[i+1][lastCol] + costMatrix[i][lastCol];
			for(int j=mat[0].length-2; j>=0; j--){
				mat[i][j] = costMatrix[i][j] + Math.min(mat[i+1][j+1],
						Math.min(mat[i+1][j], mat[i][j+1]));
			}
		}
		return mat[0][0];
	}
}

int[,] m = new int[3,3]
FindMinimumPath(m, 0, 0, 3, 3)

public static int FindMinimumPath(int[,] m, int x, int y, int tx, int ty)
        {
            int path1 = int.MaxValue;
            int path2 = int.MaxValue;
            int path3 = int.MaxValue;
            
            if(x+1 == tx && y+1 == ty)
                return m[x,y];
            
            if(x+1 < tx)
              path1 = FindMinimumPath(m, x+1, y, tx, ty);
            
            if(y+1 < ty)
              path2 = FindMinimumPath(m,x,y+1, tx,ty);
            
            if(x+1 < tx & y+1 < ty)
              path3 = FindMinimumPath(m, x+1, y+1, tx, ty);
            
            return m[x,y] + Math.Min(path1, Math.Min(path2, path3));
            
        }

We can create directed graph from the matrix. like the value to the next node as the cost of traversal. Then we can use standard algorithms like Dijkstra’s Algorithm , Prim’s Algorithm etc to find out the path between the start and end node.

int GetMinimalCost(vector<vector<int>>& grid)
{
	for (int i = 0; i < grid.size(); i++)
	{
		for (int j = 0; j < grid[i].size(); j++)
		{
			if (i == 0 && j > 0)
				grid[i][j] += grid[i][j-1];

			if (j == 0 && i > 0)
				grid[i][j] += grid[i-1][j];

			if (i > 0 && j > 0)
				grid[i][j] += min(min(grid[i][j-1], grid[i-1][j]), grid[i-1][j-1]);
		}
	}

	return grid[grid.size()-1][grid[0].size()-1];
}

int main()
{
	vector<vector<int>> grid;
	int arr[3][3] = {{4,5,6},{1,2,3},{0,1,2}};
	for (int i = 0; i< 3; i++)
	{
		vector<int> vArr(begin(arr[i]), end(arr[i]));
		grid.push_back(vArr);
	}

	int cost = GetMinimalCost(grid);

	return 0;
}

int minPathSum(vector<vector<int> > &A)
{
int m = A.size();
int n = A[0].size();
vector<vector<int>> dp(m, vector<int>(n,0));

dp[0][0] = A[0][0];

for(int i=1;i<m;i++)
dp[i][0] = A[i][0] + dp[i-1][0];
for(int i=1;i<n;i++)
dp[0][i] = A[0][i] + dp[0][i-1];

for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + A[i][j];
}
}

return dp[m-1][n-1];

}

I think your code will give incorrect result for:
4, 2, 0
1, 3, 0
4, 1, 2

in this case: your code will give: 4+1+3+0+2 : 10
but ans should be: 4+2+0+0+2 : 8

correct me, if i'm understanding the question wrong.

the before comment was meant for @mk

Can someone tell me why i'm not able to give comments on reply? I have tried several times, but it doesn't take it.

the total cost should be minimum right? Then why is everybody taking min of(right, down , diagonal) ?

the total cost should be minimum, right?
Why is everybody taking min of {right,down and diagonal} ?
take this example:
{3,2,0}
{1,3,1}
{4,5,2}
If we try with everybody's method, then it will give 3+1+3+1+2
but min cost is: 3+2+0+1+2

can op shed some light on it?

To me, the idea is to find ALL POSSIBLE ways of going from the upper left to the lower right corner, and to keep the cost of each way in a vector.
Then we find the minimal vector element.
We can traverse the matrix a directed graph using a recursion.

int findMinCost(int[][] inputMatrix)
{
  if (inputMatrix == null || inputMatrix.length == 0)
    return -1;

  int[][] minCost = new int[inputMatrix.length][inputMatrix[0].length];

  minCost[0][0] = inputMatrix[0][0];
  for (int i = 1; i < inputMatrix.length(); i++)
  {
    minCost[0][i] = minCost[0][i-1] + inputMatrix[0][i];
  }

  for (int i = 1; i < inputMatrix[0].length(); i++)
  {
    minCost[i][o] = minCost[i-1][0] + inputMatrix[i][0];
  }

  for (int i = 1; i < inputMatrix.length(); i++)
  {
    for (int j = 1; j < inputMatrix[0].length(); j++)
    {
       minCost[i][j] = Math.min(minCost[i-1][j-1], Math.min(minCost[i-1][j], minCost[i][j-1])) + inputMatrix[i][j];
    }
  }

  return minCost[inputMatrix.length - 1][inputMatrix[0].length -1];
}

mat = [[4,5,6],[1,2,3],[0,1,2]]

def minPath(mat):
    m,n = len(mat),len(mat[0])
    cost = [[0]*n for i in range(m)]
    for i in range(0,m):
        for j in range(0,n):
            if i == 0 and j == 0:
                cost[i][j] = mat[i][j]
            elif i == 0:
                cost[i][j] = mat[i][j] + cost[i][j-1]
            elif j == 0:
                cost[i][j] = mat[i][j] + cost[i-1][j]
            if i > 0 and j > 0:
                cost[i][j] = mat[i][j] + min(cost[i-1][j-1],cost[i-1][j],cost[i][j-1])
    return cost[m-1][n-1]

This is simple. Compute from bottom-right all the way to the top - left.

int[,] best = new int[R, C];
Arrays.fill(best[R], Integer.MAX_VALUE);
for(int i =0; i < R; ++i)
  best[i, C] = Integer.MAX_VALUE;

for(row = R-1; row >= 0; row--)
{
  for(col = C-1; col >= col; col--)
  {
    best[row][col] = min (best[row+1][col], best[row][col+1], best[row+1][col+1]);
  }
}
return best[0][0];

private static int[] getPath(int i, int j, int[] currPath) {
if (i <= 2 && j <= 2) {
final int currValue = matrix[i][j];
final int[] currTotalPath = mergeArrs(currPath, new int[]{currValue});
if (i == 2 && j == 2) {
return currTotalPath;
}

int arrRight[] = getPath(i, j + 1, currTotalPath);
int arrDown[] = getPath(i + 1, j, currTotalPath);
int arrDiag[] = getPath(i + 1, j + 1, currTotalPath);
return getMin(arrRight, arrDown, arrDiag);
} else {
return mergeArrs(currPath, new int[]{-1});
}
}

Its a DP problem.
F(i,j) = Min (F(i-1,j), F(i-1,j-1), F(i,j-1))

We need to find all the possible paths and then find the minimum cost path
My solution is in Scala
Note: the M x N matrix is modeled as a vector but accessed with x,y by vector(y*m + x), fairly common technique

val xSize = m
val ySize = n

val inputMatrix:Vector = Vector(4,5,6,1,2,3,0,1,2)
def getValueFromPos(p:Position): Int = {
	inputMatrix(p.y*xSize + p.x)
}

type Position = (Int, Int)

trait Move {
	def execute(p: Position): Position
}

case class Right extends Move {
	def execute(p: Position): Position = (p.x + 1, p.y)
}
case class Down extends Move {
	def execute(p: Position): Position = (p.x, p.y + 1)
}
case class Diagnol extends Move {
	def execute(p: Position): Position = (p.x + 1, p.y + 1)
}
def getMoves(pos:Position): List[Moves] {
	if(pos.x < m-1) Right ++
	if(pos.y < n-1) Down ++
	if(pos.x < m-1 && pos.y < n-1) Diagnol
}

class Path(history: List[Moves], endPos: position, sumCost: Int) {
	def extend(m: Move) = new Path(m :: history, m.execute(endPos), sumCost + getValueFromPos(m.execute(endPos)))
}
val initialPath: Path = new Path(Nil, (0,0), 0)

//To get all the paths 
def getAllPaths(paths: List[Path]): List[Path] = {
	if(paths.isEmpty) List[]
	else {
		val morePaths = for {
						path <- paths
						next <- path.endPos getMoves map path.extend
						} yield next
	paths :: getAllPaths(morePaths)
}

//To find min path between two paths
def minPath(path1: Path, path2: Path) {
	if(path1.sum < path2.sum) path1
	else path2
}

//Solution to find minimum path
val minPath = getAllPaths(List(initialPath)).reduceLeft(_ minPath _)