通过需要考虑多种成本的矩阵的最佳路径

例如给出以下矩阵：

[[[0, 8], [0, 3], [0, 8]],
 [[8, 0], [3, 0], [0, 5]],
 [[0, 1], [0, 6], [0, 0]]]

对于每个元组，第一个数字是食物，第二个数字是水。我需要从右下角到左上角，并且只能向上或向左移动。

我需要收集尽可能多的食物和水，这样我才能活得尽可能长。为了生存，我每天需要 1 份食物和 1 份水，因此，如果我可以在一条导致 (7,4) 的路径和一条导致 (6,6) 的路径之间进行选择，则正确的选择是 (6,6 ）因为这可以让我活 6 天。

如何通过所述矩阵找到最佳路径？

我当前的代码在下面，但它不起作用（它找到了一条成本非常高的路径，但不是最高的），我不知道如何去做。我不知道如何开始实现它，尽管我被告知要避免递归。

def maxSuppliesPath(matrix):
n = len(matrix) - 1
bestPath = matrix

# Initialize first column of bestPath array
for i in range(1, n + 1):
    if bestPath[i][0] == 0:
        bestPath[i][0] = bestPath[i - 1][0]
    else:
        bestPath[i][0] = (bestPath[i][0][0] + bestPath[i - 1][0][0], bestPath[i][0][1] + bestPath[i - 1][0][1])

# Initialize first row of bestPath array
for j in range(1, n + 1):
    if bestPath[0][j] == 0:
        bestPath[0][j] = bestPath[0][j - 1]
    else:
        bestPath[0][j] = (bestPath[0][j - 1][0] + bestPath[0][j][0], bestPath[0][j - 1][1] + bestPath[0][j][1])



# Construct rest of the bestPath array
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if min(bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1]) > min(
                bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1]):
            bestPath[i][j] = (bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1])
        else:
            bestPath[i][j] = (bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1])

return min(bestPath[n][n][0], bestPath[n][n][1])

解决问题的第一步是了解如何遍历矩阵。下图显示了从起点到其他点的距离。

请注意，等距点排列在对角线上。给定一个set（叫它A）代表一条对角线，下一条对角线上的点（称之为B) 的发现如下：

for each point in set A
    if the x coordinate is greater than zero
        add (x-1, y) to set B
    if the y coordinate is greater than zero
        add (x, y-1) to set B

在示例中，表示对角线的集合应如下所示：

[(2, 2)]                  // starting position
[(1, 2), (2, 1)]          // after 1 move
[(2, 0), (1, 1), (0, 2)]  // after 2 moves
[(0, 1), (1, 0)]          // after 3 moves
[(0, 0)]                  // after 4 moves

下图显示了可以使用多少条不同的路径来到达矩阵中的每个点。路径数与中的数字相同帕斯卡三角形。就这个问题而言，唯一重要的是数字增长很快，因此我们需要减少计数。

为了减少路径计数，我们需要在遍历矩阵时剔除非生产性路径。这是通过比较元组来完成的，其中每个元组都包含食物和水。一个元组(F,W)支配一个元组(f,w) iff F >= f AND W >= w.

例如，考虑矩阵中的中心位置。我们可以通过先向上然后向左移动，或者先向左然后向上移动来到达该点。先向上再向左移动的产量（食物、水）为（3,5），而先向左然后向上移动的产量（3,6）。 (3,6)支配(3,5)，所以我们只需要考虑(3,6)。所以经过两次移动之后，我们就出现了下图所示的情况。请注意，我们在中心位置只有 1 个元组，而不是帕斯卡三角形预测的两个元组。

经过三步后，我们得到如下所示的情况。第三对角线上的每个点都有两个元组。这是必要的，因为其中一个元组有更多的食物，另一个元组有更多的水，所以两个元组都不会支配另一个元组。

经过四次移动后，我们有四种可能的答案，选择最好的只是一个简单的比较问题min(food, water)对于每个元组。