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

Question

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

       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路线,问题就更难了.

我认为我从最强大的数字开始从底部开始,但很快我意识到,最大路线成本不是必须开始或最终大数.

然后我想也许可以使用secoundary索引(在哪里可以从一个数字进一步),但我甚至没有实现,因为我认为它仍然使用了很多资源而不是最优.

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

Answer 1

将您的金字塔想像成一棵树，其根在金字塔的顶部：我想您希望从根到任何叶节点（金字塔的底部）的路线成本最高。好的，它实际上不是一棵树，因为一个节点可能有两个父节点，实际上您最多可以从level的i两个节点到达该level的节点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) }

c(h,k)当您到达矩阵之外的位置时，其中0为零。从本质上讲，我们说到位置(i,j)上到达节点的最大成本是节点本身的成本加上在水平上到达其两个可能的父节点的成本之间的最大值i-1。

这是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

从c您看到的最昂贵的溃败成本为48（并且您有两个）。