java - 递归地从矩阵中检索权重最低的路径

Question

假设我有一个n^n 矩阵。在每个单元格中都有一个正数，我需要检索权重最低的路径。

path 是从 matrix[0][0] 开始到 matrix[matrix.length-1][matrix[0] 结束的每条路径.length-1]，没有对角线。

路径的

权重是其单元格中所有数字的数量。

例如，假设我有这个矩阵:

mat = {{1,2},{3,4}};

所以 {1,2,4} 是一个路径，而 {1,3,4} 是另一个路径.

第一条路径的权重是7(1+2+4)，第二条路径的权重是8(1+3+4)，所以该函数将返回 7。

我需要递归地解决它。伪代码应该是这样的:

if i > matrix.length-1 || i < 0 || j > matrix[0].length-1 || j < 0
//then I passed the borders, so I need to step back.
if i == matrix.length-1 && j == matrix[0].length-1
//Then I reached the last cell, and I need to retrieve sum

然后调用四个递归调用:

public static int smallPath(a, i+1, j, sum);
public static int smallPath(a, i, j+1, sum);
public static int smallPath(a, i-1, j, sum);
public static int smallPath(a, i, j-1, sum);

那我需要取回一些东西，什么？

我知道这不是最新的，但这是一般的想法，有人可以帮我解决这个问题吗？谢谢!

Answer 1

我不确定这是否是最有效的解决方案，但您应该考虑一下:

1. 你必须先测试随机方式并得到它的和。
2. 系统地处理问题。尝试另一个，如果它的 sum 在进度中较大，则停止它并尝试另一个。
3. 如果找到最小的sum 路，捕获它的sum(和方向)并尝试另一个，直到没有路为止
4. 你有结果:)

此解决方案适用于直接 路径。我的意思是你总是向右或向下走。不返回(向上或向左)- 如果您从左上角的单元格开始并在右下角的单元格结束。

检查差异:

第一个很明显，最小的总和是 18 (3+2+1+0+1+2+4+3+2) .. 但在第二个中，结果是根据我的直接方法 107 和不是 17，因为正确的解决方案是。

一般来说，在这种情况下找到最佳解决方案非常复杂，您必须指定是否设置任何限制。