Java 中的最小成本路径问题

Java 中的最小成本路径问题是面试中被问到最多的问题之一。在这个问题中，会提供一个矩阵（costMatrix[][]），该矩阵表示 costMatrix[][] 中每个单元格的成本。任务是从左上角走到右下角，使得成本最小。我们需要返回最小成本。从一个单元格移动到另一个单元格的规则是，一次只能向左、向下或斜对角方向移动一个单元格。例如，从当前单元格 costMatrix[x][y]，我们只能移动到以下单元格之一：costMatrix[x][y + 1]（向左方向）、costMatrix[x + 1][y]（向下方向）和 costMatrix[x + 1][y + 1]（斜对角方向）。

例如，在以下矩阵中

从左上角单元格（成本为 1）到右下角单元格（成本为 7）有以下几种路径。

1 -> 6 -> 9 -> 5 -> 7		Total Cost = 1 + 6 + 9 + 5 + 7 = 28
1 -> 6 -> 15 -> 5 -> 7		Total Cost = 1 + 6 + 15 + 5 + 7 = 34
1 -> 6 -> 15 -> 3 -> 7		Total Cost = 1 + 6 + 15 + 3 + 7 = 32
1 -> 6 -> 15 -> 7		Total Cost = 1 + 6 + 15 + 7 = 29
1 -> 6 -> 5 -> 7		Total Cost = 1 + 6 + 5 + 7 = 19
1 -> 2 -> 15 -> 3 -> 7		Total Cost = 1 + 2 + 15 + 3 + 7 = 28
1 -> 2 -> 15 -> 5 -> 7		Total Cost = 1 + 2 + 15 + 5 + 7 = 30
1 -> 2 -> 15 -> 7		Total Cost = 1 + 2 + 15 + 7 = 25
1 -> 2 -> 2 -> 3 -> 7		Total Cost = 1 + 2 + 2 + 3 + 7 = 15
1 -> 2 -> 3 -> 7		Total Cost = 1 + 2 + 3 + 7 = 13

在上述所有路径中，最后一条路径（1 -> 2 -> 3 -> 7，总成本：13）的成本最低。因此，13 是上述矩阵的所需答案。

注意：假设矩阵中任何单元格的成本始终是非负的。

方法

有两种方法可以解决这个问题：一种是递归方法，另一种是迭代方法（使用动态规划）。让我们从递归方法开始。

实现：递归

递归方法也是暴力方法。在这种方法中，我们将遍历所有路径，并在这些路径中选择成本最低的路径。请看下面的程序。

文件名： MinCostPath.java

输出

For the following matrix: 
1 2 2 
6 15 3 
9 5 7 

The minimum cost path from the top-left to the bottom-right is: 13

For the following matrix: 
10 12 20 
16 5 13 
19 50 17 

The minimum cost path from the top-left to the bottom-right is: 32

复杂度分析：在上述程序中，一次递归调用会产生三次递归调用。因此，上述程序的 time complexity 是指数级的。指数级 time complexity 很大，在处理大量数据时应避免。因此，应该进行优化以降低 time complexity。

如果我们观察上面的程序，我们会发现有许多子问题被计算了多次，这导致了指数级的 time complexity。请看以下内容。

我们看到 minCostPath(1, 1) 出现了多次。因此，我们需要多次计算 minCostPath(1, 1) 的值。如果我们进一步扩展递归调用，我们会发现许多递归调用是多余的，应该避免。下面的程序展示了如何避免重复的递归调用。它使用了带有记忆化技术的递归。

文件名： MinCostPath1.java

输出

For the following matrix: 
1 2 2 
6 15 3 
9 5 7 

The minimum cost path from the top-left to the bottom-right is: 13

For the following matrix: 
10 12 20 
16 5 13 
19 50 17 

The minimum cost path from the top-left to the bottom-right is: 32

复杂度分析：在上述程序中，一次递归调用也会产生三次递归调用。然而，并非每次递归调用都会执行到底。由于我们避免了重复子问题的计算；因此，上述程序的 time complexity 大约为 O(row * column)，其中 row 和 column 是 cost matrix 的行数和列数，这需要一些额外的空间。使用的额外空间为 O(row * column)。

实现：迭代

在这种方法中，我们将使用动态规划来解决最小成本路径问题。请看下面的程序。

文件名： MinCostPath2.java

输出

For the following matrix: 
1 2 2 
6 15 3 
9 5 7 

The minimum cost path from the top-left to the bottom-right is: 13

For the following matrix: 
10 12 20 
16 5 13 
19 50 17 

The minimum cost path from the top-left to the bottom-right is: 32

复杂度分析：在上述程序中，有许多单 for 循环。然而，还有一个二重 for 循环。因此，上述程序的 time complexity 为 O(row * column)，其中 row 是输入数组中的总行数，column 是输入数组的列数。此外，程序使用了一些额外的空间（一个二维数组：totalCost[][]），这使得程序的 space complexity 为 O(row * column)。

请注意，如果允许修改输入数组，那么我们可以放弃二维数组（totalCost[][]）以将程序的 space complexity 降低到 O(1)。程序的 time complexity 保持不变。下面的程序展示了这一点。

文件名： MinCostPath3.java

输出

For the following matrix: 
1 2 2 
6 15 3 
9 5 7 

The minimum cost path from the top-left to the bottom-right is: 13

For the following matrix: 
10 12 20 
16 5 13 
19 50 17 

The minimum cost path from the top-left to the bottom-right is: 32