Minimum cost via matrix
Matrix:
6 9 3
4 8 2
3 5 10
You can start with any integer on the first row, you can only go down the matrix and add left, right, or just below the previous number. For example, you start at 9, you can either go to 4.8 or 2. I figured out how to get the results matrix
Matrix:
6 9 3
10 11 5
13 10 15
The shortest path is obviously 3> 2> 5, which corresponds to 3> 5> 10 on the results matrix. I want to store the coordinates of the cheapest path in an ArrayList. In this case, it will be [0,2,1,2,2,1]. This is what I have so far. The question is, where do you add values to the ArrayList?
private static ArrayList<Integer> minCost(int cost[][])
{
ArrayList<Integer> minValues = new ArrayList<>();
int n = cost.length;
int m = cost[0].length;
int i, j;
int tc[][] = new int[m][n];
for (i = 0; i <= n - 1; i++) {
tc[0][i] = cost[0][i];
}
for (i = 1;i <= n - 1; i++) {
for (j = 0; j <= m - 1; j++) {
if(j ==0){
tc[i][j] = Math.min(tc[i - 1][j],
tc[i-1][j + 1])
+ cost[i][j];
}
else if(j == m-1){
tc[i][j] = Math.min(tc[i - 1][j - 1],
tc[i - 1][j])
+ cost[i][j];
}
else{
tc[i][j] = min(tc[i - 1][j - 1],
tc[i - 1][j],
tc[i-1][j + 1])
+ cost[i][j];
}
}
}
return minValues;
}
source to share
The values should be added to the array list after creating the entire overall cost matrix as you did.
The path will be restored back from the position on the bottom row that has the lowest total cost. This will be the last pair of coordinates in the resulting array list.
Subsequently, its predecessor must be identified. This can be done by checking which of the adjacent cells in the previous row has a total cost, which, when added to the current cell's cost, generates the required total cost.
In the example shown, the optimal path would end in the bottom row in cell (2, 1), because this is the cell with the lowest total cost from the bottom row (its total cost is 10). The previous cell must have one that has total_cost = 10 - cost (2, 1) = 5. There is one candidate with this property among the adjacent cells from row 1, that is, cells (1, 2).
The process should continue as follows: search the cells of the path one by one in reverse order until the path is complete (i.e. it reaches the first line).
Some notes:
-
if at some point there are multiple optimal predecessor candidates (both with the same total cost), then either one can be selected. Each of them would create an optimal path with the same total cost.
-
to create the final path in the desired order, the position found in each step can be added at the beginning of the array (to avoid having to do the opposite at the end).
source to share