我正在研究欧拉项目.特别是#18.
总而言之,我们的想法是从三角形中找到最大路径:
3
7 4
2 4 6
8 5 9 3
3 + 7 + 4 + 9 = 23.
对此进行阅读,大多数人表示这是通过从下到上的工作而不是使用从上到下工作"贪婪"的算法来正确解决的.
我可以理解,从顶部开始向下选择你发现的最大值是"短视",可能不是整体最大值.
但为什么从底部到顶部的方法更好？
在我看来,它遇到了同样的问题.
例如,在示例中的三角形中,我们将得到(从底部开始):
9 + 6 + 4 + 3 = 22 <23
那么为什么要从下到上开始呢？
algorithm ×1