寻找价值最高的路线

Question

给定下面的数据，找到从左下角到右上角的最高价值路线。

[{ 0, 0, 0, 6 }, 

  { 2, 0, 0, 2 }, 

  { 0, 1, 1, 1 }, 

  { 3, 0, 0, 0 }]

go can only move right (east) or up (north)

Highest value route here is 3 -> 0 -> 1 -> 1 -> 1 -> 2 ->6 = 14

我应该如何处理这个问题。我下面作为伪代码的方法是否正确？

max = 0

array = defined_array 

i = len(array)

k = 0  

def path(i,j):

total = 0

    for j in range(4):

        k = j;

        total = total + int(array[i][j])    

        if total > max:

            max = total

    return path(--i,k)

key= 3

def path(i,j):

    for i in range(i):

        for j in range(array[i]):

            total = total + array[i][j]

Answer 1

我根本没有得到你的方法。这就是简单动态规划问题。将其视为二维数组Arr[4][4][{ 0, 0, 0, 6 },   { 2, 0, 0, 2 },   { 0, 1, 1, 1 },   { 3, 0, 0, 0 }]制作另一个 4*4 的 dp 数组您需要做的第一件事是初始化基本案例。所以第一列和最后一行是我们的基本情况。dp[0][3]=Arr[0][3];在此之后为第一列dp[i][0]=dp[i+1][0]+Arr[i][0];对于最后一行dp[3][i]=dp[3][i-1]+Arr[3][i];对于其他值dp[i][j]=max(dp[i][j-1],dp[i+1][j])+Arr[i][j];，我们将选择最大值。我们的 dp 数组看起来像这样，答案是 14[{ 5, 5, 5, 14 },   { 5, 5, 5, 8 },   { 3, 4, 5, 6 },   { 3, 3, 3, 3 }]

Answer 2

这基本上是通过图找到最优路径（在这种情况下：最高值路径）的问题。有一些众所周知的方法可以找到最短路径，例如Dijkstra 算法和Bellman-Ford 算法。对于您的图是有向图和无环图（“DAG”），我在这里和这里发现了两个讨论，指出这些算法不能仅仅从最小到最大“反转”以找到最长的路径，但是如果你转换你的路径它确实有效将每个权重（值）反转为负数的图形。另请参阅关于最长路径问题的 Wikipedia 文章。