在一个矩阵中找到最小成本

Question

在一个矩阵中找到最小成本

javaalgorithmmatrixdynamic-programmingminimum

3

Matrix:
6 9 3
4 8 2
3 5 10

你可以从第一行的任意整数开始，只能向下移动到左、右或直接下方的前一个数字，并将它们相加。例如，你从9开始，可以选择移动到4、8或2。

我已经想出如何得到结果矩阵，即：

Matrix:
6 9 3
10 11 5
13 10 15

最短路径显然是3>2>5，对应于结果矩阵上的3>5>10。我想把最便宜的路径坐标存储在ArrayList中。在这种情况下，它将是[0,2,1,2,2,1]。目前为止，我的问题是在什么地方将值添加到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;
    }

- Andy9673

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- danbanica · Accepted Answer

在整个总成本矩阵生成后，应像您已经做过的那样将值添加到数组列表中。路径将向后重建，从具有最小总成本的底行位置开始。这将是结果数组列表中的最后一对坐标。

然后，应该识别它的前任。这可以通过检查先前行中哪些相邻单元格具有总成本，当将当前单元格的成本与其相加时，生成所需的总成本来完成。

在提供的示例中，最佳路径必须最终在底部行的单元格（2,1）中结束，因为这是底部行中总成本最小的单元格（其总成本为10）。上一个单元格需要是具有total_cost = 10-cost（2,1）= 5的单元格。在第1行的相邻单元格之间有一个符合此属性的单个候选单元格，即单元格（1,2）。

这样，该过程应该继续进行，逆序逐个找到路径单元格，直到完整路径（即到达第一行）。

一些备注：

- 如果在某个点存在多个最优的前任候选者（都具有相同的总成本），则可以选择其中任何一个。每个人都会生成具有相同总成本的最优路径。 - 要按所需顺序创建最终路径，则可以在每个步骤中找到的位置添加到数组的前面（以避免在最后执行反转）。