我正在研究一个欧拉项目。具体来说#18。
总而言之，这个想法是从三角形中找到最大路径：
3
7 4
2 4 6
8 5 9 3
3 + 7 + 4 + 9 = 23。
读到这里，大多数人表示，通过从下到上工作可以正确解决这个问题，而不是使用从上到下“贪婪”工作的算法。
我可以理解，从顶部开始向下选择您找到的最大值是“短视”的，并且可能不是整体最大值。
但为什么从下到上的方法更好呢？
在我看来，它也面临着同样的问题。
例如，在示例中的三角形中，我们会得到（从底部开始）：
9+6+4+3=22
那么为什么要从下往上开始呢？
这就是所谓的动态规划。
你有这样的三角形：
3
7 4
2 4 6
8 5 9 3
当您从底部移动到顶部时，您可以计算最后一次迭代的最佳选择。
在这种情况下，您将选择最后一行8 5 9 3并最大化除上一行之外的总和。
迭代 1：
假设您正在last-1 step.
你有线2 4 6，让我们迭代一下。
From 2，您可以前往8或 5，所以8更好（最大化 2 的结果），因此您计算出第一个总和 8 + 2 = 10。
From 4，您可以转到 5 或9, so 9更好（最大化 4 的结果），因此您计算出第二个总和 9 + 4 = 13。
From 6，您可以前往9或 3，所以9又更好了（最大化 6 的结果），因此您计算出第三个总和 9 + 6 = 15。
这是第一次迭代的结束，您得到了总和行10 13 15.
现在你有了较低维度的三角形：
3
7 4
10 13 15
现在继续下去，直到获得一个值，即 23。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
