java - 如何在二维矩阵中找到成本最低的路径

Question

我有一个挑战，目标是获得最低成本的路径。 该路径可以水平或对角线前进。不是垂直的。像下面。 并且第一行和最后一行也是相邻的。

例如见下面的矩阵:

output for 1st matrix :
16
1 2 3 4 4 5-->path row number

output for second matrix:
11
1 2 1 5 4 5-->path row number

我是用 java 做的，我得到了最低路径，但没有得到使用行号打印路径的路径。

int minCost(int cost[r][r], int m, int n)
{
   if (n < 0 || m < 0)
      return Integer.MAX_VALUE;;
   else if ((m == r-1 && n == c-1)|| n+1>=c)
      return cost[m][n];
   else
      return cost[m][n] + min( minCost(cost, m+1>=r?r-1:m+1,n+1),
                                         minCost(cost, m,n+1),
                                minCost(cost, m-1>=0?m-1:r-1,n+1));
    }
// calling it 
minCost(cost, 0, 0);

如何获取最短路径的行号？

Answer 1

您的算法效率很低。我能想到的最好的解决方案是向后计算(从右到左)。考虑第二个矩阵的右侧 2 列:

8 6
7 4
9 5
2 6 
2 3

如果现在我们在值为 8 的单元格上，下一步可以是 6/4/3。当然我们选择 3 是因为我们想要更小的成本。如果现在我们在值为 7 的单元格上，下一步可以是 6/4/5，我们将选择 4。因此两列可以合并为一列:

11   //8+3
11   //7+4
13   //9+4
5    //2+3
5    //2+3

现在重复最后两列:

2  11
2  11
9  13
3  5
1  5

最后将矩阵合并为一列，列中最小的值具有最低的成本。