**Objective: **Given a 2D-matrix where each cell has a cost to travel. You have to write an algorithm to find a path from left-top corner to bottom-right corner with minimum travel cost. You can move only right or down.

In the solution we will see that how dynamic programming is much better approach than recursion. Don’t get me wrong, even I like recursion a lot ðŸ™‚

**Example**:

**Approach**:

This problem is similar to** Find all paths from top-left corner to bottom-right corner.**

We can solve it using Recursion ( return Min(path going right, path going down)) but that won’t be a good solution because we will be solving many sub-problems multiple times. Since at every cell we have 2 options the time complexity will O(2^{n}).

**Dynamic Programming:**

Create a solution matrix of the same size as given matrix.

We will fill this matrix in **Bottom-up** manner.

**Given**: arrA[][].

At every cell, we have two options (go right or down) and we will choose the minimum of these two. So for any i,j cell solution[i][j] = A[0][j] if i=0 , first row = A[i][0] if j=0, first column = A[i][j] + Min(solution[i-1],[j] , solution[i][j-1]) if i>0 && j>0 See the code for better Explanation.

Time Complexity: O(n^{2}).

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class MinCostPath { | |

public static int find(int[][] A) { | |

int[][] solution = new int[A.length][A.length]; | |

solution[0][0] = A[0][0]; | |

// fill the first row | |

for (int i = 1; i < A.length; i++) { | |

solution[0][i] = A[0][i] + solution[0][i – 1]; | |

} | |

// fill the first column | |

for (int i = 1; i < A.length; i++) { | |

solution[i][0] = A[i][0] + solution[i – 1][0]; | |

} | |

// path will be either from top or left, choose which ever is minimum | |

for (int i = 1; i < A.length; i++) { | |

for (int j = 1; j < A.length; j++) { | |

solution[i][j] = A[i][j] | |

+ Math.min(solution[i – 1][j], solution[i][j – 1]); | |

} | |

} | |

return solution[A.length – 1][A.length – 1]; | |

} | |

public static void main(String[] args) { | |

int[][] A = { { 1, 7, 9, 2 }, { 8, 6, 3, 2 }, { 1, 6, 7, 8 }, | |

{ 2, 9, 8, 2 } }; | |

System.out.println("Minimum Cost Path " + find(A)); | |

} | |

} |

Output: Minimum Cost Path 29

http://www.ideserve.co.in/learn/minimum-cost-path

Here is a nice detailed explanation of the algorithm.

I believe the answer is 14, not 29. Can you check? I get that when I run it manually and with the program.

Also for the following, why are you setting 0,0 first rather than setting the first row with i=0 to length and first column with i = 0 to length? I think when you do i=1, you are setting the values of the second row and second column. How can solution[0,i-1] even have a value if you haven’t initialized it yet? e.g. for solution[0, 2]

solution[0][0] = A[0][0];

// fill the first row

for (int i = 1; i < A.length; i++) {

solution[0][i] = A[0][i] + solution[0][i – 1];

}

// fill the first column

for (int i = 1; i < A.length; i++) {

solution[i][0] = A[i][0] + solution[i – 1][0];

}

I tried this and it worked:

public static void MinCostPath()

{

int[,] arr = new int[,] { { 1, 7, 9, 2 },

{ 8, 6, 3, 2 },

{ 1, 6, 7, 8 },

{ 2, 9, 8, 2 } };

int[,] solution = new int[arr.GetLength(0), arr.GetLength(1)];

for (int row = 0; row < arr.GetLength(0); row++)

{

solution[row, 0] = arr[row, 0];

}

for (int col = 0; col < arr.GetLength(1); col++)

{

solution[0, col] = arr[0, col];

}

for (int row = 1; row < arr.GetLength(1); row++)

{

for (int col = 1; col < arr.GetLength(0); col++)

{

solution[row, col] = arr[row, col] + Math.Min(solution[row – 1, col], solution[row, col – 1]);

}

}

Console.WriteLine("Minimum cost of traveling through the array is: {0}", solution[solution.GetLength(0)-1, solution.GetLength(1)-1]);

}

when you say answer is 14, whats the path