从递归的矩阵中检索具有最低权重的路径

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. 系统地采取方法。尝试另一种，如果进程中其总和较大，则停止并尝试另一种。
3. 如果您找到最小的总和方式，请捕获其总和（和方向）并尝试另一种方式，直到没有剩余的方式为止
4. 你已经得到结果了:)

该解决方案适用于直接路径。我的意思是你总是向右或向下迈出一步。不返回（向上或向左）- 如果您从左上角的单元格开始并以右下角的单元格结束。

检查差异：

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

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