I have an mXn matrix, starting from [0][0] cell I need to go to [m][n] through the lowest possible cost path, where costs are cell values (integer, greater than 0). Only moves possible are right, down and diagonally down.
I have tried Dynamic programming approach to find the lowest cost but could not be able to print the path.
e.g. for matrix {(3,2,8),(1,9,7),(0,5,2),(6,4,3)} its giving cost as 11, but as my approach converting the matrix to cost matrix, the path is printing wrong.
expected output:
cost: 11
path: B B D R (i.e. the traversal movements, Below, Down, Rigth)
The code attached here I have found in the internet. Please provide me snippet to print the path.
What I have tried:
public static int minimumCostPathDP(int[][] costMatrix, int m, int n) {
int[][] minimumCostPath = new int[m+1][n+1];
minimumCostPath[0][0] = costMatrix[0][0];
for (int i = 1; i <= m; i++) {
minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0];
}
for (int j = 1; j <= n; j++) {
minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
minimumCostPath[i][j] = costMatrix[i][j]
+ minimum(minimumCostPath[i - 1][j - 1],
minimumCostPath[i - 1][j],
minimumCostPath[i][j - 1]);
}
}
return minimumCostPath[m][n];
}
public static int minimum(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
public static void main(String[] args) {
int[][] costMatrix = { { 3, 2, 8 }, { 1, 9, 7 }, { 0, 5, 2 }, {6, 4, 3} };
System.out.println("Minimum cost: " + minimumCostPathDP(costMatrix, 3, 2));
}
}