如何确定 n 高数字金字塔中的最大路线成本

我有一个像这样的数字金字塔

       7
      4 8
     1 8 9
    2 4 6 7
   4 6 7 4 9
  4 9 7 3 8 8

routes: 32

每个数字都按其系列中的强大程度进行索引。

 0 ( 9 => 1 ) 1 ( 8 => 5 ) 2 ( 8 => 4 ) 3 ( 7 => 2 ) 4 ( 4 => 0 ) 5 ( 3 => 3 )
 0 ( 9 => 4 ) 1 ( 7 => 2 ) 2 ( 6 => 1 ) 3 ( 4 => 3 ) 4 ( 4 => 0 )
 0 ( 7 => 3 ) 1 ( 6 => 2 ) 2 ( 4 => 1 ) 3 ( 2 => 0 )
 0 ( 9 => 2 ) 1 ( 8 => 1 ) 2 ( 1 => 0 )
 0 ( 8 => 1 ) 1 ( 4 => 0 )
 0 ( 7 => 0 )

在这个金字塔中有 2^(n-1) 条路线（每个数字可以走 2 条路） 如果金字塔高这么低，你很容易计算出所有的路线，并相互比较。但如果你有一个 50 高的金字塔，有 562949953421312 条路线，那么问题就有点困难了。

我以为我从最底层开始，从最强大的数字开始，但很快我意识到，最大路线成本不一定以大数字开始或结束。

然后我想也许二级索引（你可以从一个数字进一步了解哪里）会有所帮助，但我什至没有实现它，因为我认为它仍然使用大量资源并且不是最佳的。

现在我很困惑如何重新开始思考这个问题......任何建议表示赞赏

将您的金字塔视为一棵树，根位于金字塔顶部：我认为您希望从根到任何叶节点（金字塔底部）具有最大成本的路线。好吧，它实际上不是一棵树，因为一个节点可能有两个父节点，实际上您可以在级别上访问节点i级别上最多有两个节点i-1.

不管怎样，我认为你可以通过动态规划来计算出成本最大的路线。让我以类似矩阵的方式重写您的数据：

7 
4 8 
1 8 9 
2 4 6 7 
4 6 7 4 9 
4 9 7 3 8 8

并让矩阵的缺失元素为0。我们称这个矩阵为v（对于值）。现在您可以构建一个矩阵c（费用）其中c(i,j)是到达位置处的树节点的最大成本(i,j)。您可以使用以下递归式来计算它：

c(i,j) = v(i,j) + max{ c(i-1,j-1), c(i-1,j) }

where c(h,k)当到达矩阵外的某个位置时，值为 0。本质上我们说的是到达位置节点的最大成本(i,j)是节点本身的成本加上到达其两个可能父级的成本之间的最大值i-1.

Here is c对于你的例子：

7     
11 15    
12 23 24   
14 27 30 31  
18 33 37 35 40 
22 42 44 40 48 48

例如，我们以i=3, j=2:

c(3,2) = v(3,2) + max{ c(2,1), c(2,2) }
       = 6      + max{ 23    , 24     }
       = 30

From c您会看到最昂贵的溃败花费 48（并且您有两个）。