金字塔算法

Question

我正在尝试找到一种算法,在这种算法中,我可以通过数字金字塔,从金字塔的顶部开始,然后前进到下一行中的相邻数字,每个数字都必须添加到最终总和中.问题是,我必须找到返回最高结果的路线.

我已经尝试在下一行中查看较高的相邻数字,但这不是答案,因为它并不总能获得最佳路线.

IE

        34
      43  42
    67  89  68
  05  51  32  78
72  25  32  49  40

如果我通过最高的相邻号码,它是:

34 + 43 + 89 + 51 + 32 = 249

但是,如果我去:

34 + 42 + 68 + 78 + 49 = 269

在第二种情况下,结果更高,但我手工制作了这条路线,我无法想到在所有情况下获得最高结果的算法.

任何人都可以帮我一把吗？

(如果我没有表达自己,请告诉我)

Answer 1

从底行开始.当您从左到右时,请考虑两个相邻的数字.现在上一行并比较上面一行中两个数字之上的数字之和与下面的每个数字.选择较大的总和.

基本上,您正在查看由底行和上面的行形成的三角形.所以对于你的原始三角形,

        34
      43  42
    67  89  68
  05  51  32  78
72  25  32  49  40

左下角三角形看起来像,

  05
72  25

所以,你会增加72 + 05 = 77,因为这是间最大的一笔72 + 05和25 + 05.

同样的,

  51
25  32

会给你的51 + 32 = 83.

如果对每两个相邻的数字和上面的数字继续这种方法,则可以丢弃底行并用计算的总和替换上面的行.

所以在这种情况下,倒数第二行变为

77  83  81  127

而你的新金字塔是

      34
    43  42
  67  89  68
77  83  81  127

继续这样做,你的金字塔开始缩小,直到你有一个数字,这是你所追求的数字.

    34
  43  42
150 172 195

   34
215  237

最后,你剩下一个号码,271.