algorithm - Euler18动态算法

Question

给定数组 [5, 4, 12, 3, 11, 7, 2, 8, 1, 9] 组成一个三角形:

   5
  4 12
 3 11 7
2 8  1 9

结果应该是 5 + 12 + 7 + 9 = 31。

编写一个函数，该函数将遍历三角形并找到当您可以从一个点直接移动到左下角或右下角时最大可能的值和。

引用该链接中的动态算法: http://www.mathblog.dk/project-euler-18/

结果是 36。

  5
 4 12
 3 11 7
2 8 1 9

    5
   4 12
 11 19 16

  5
23 31

36 

我的错误在哪里？？

Answer 1

description of Problem 18从最佳路径为“左-右-右”的示例开始。所以你在每一步之后都会得到一个新的方向选择，这意味着在向右迈出第一步之后，你仍然可以自由地向左迈出第二步，最终得出5+12+11+8=36作为您示例中的最佳解决方案，大于您假设的 31。因此，计算在解决所描述的问题时是正确的。您关于只选择一次方向然后坚持该选择的假设会导致一个不同的(而且相当无聊的)问题。