欧拉项目＃18方法 [英] Euler project #18 approach
问题描述
我期待到欧拉项目。特别是＃18。
总结起来，这个想法是找到一个三角形的最大路径：
I am looking into an Euler project. Specifically #18.
To sum up, the idea is to find the max path from a triangle:
3
7 4
2 4 6
8 5 9 3
3 + 7 + 4 + 9 = 23
3 + 7 + 4 + 9 = 23.
读为此，大多数人表明，这是通过使用一种算法，从顶端作品贪婪至底部工作底部到顶部，而不是正确地解决。
Reading for this, most people indicate that this is solved correctly by working bottom to top instead of using an algorithm that works "greedy" from top to bottom.
我可以undertand从顶部开始和下降选择所述最大你发现是sortsighted未必整体最大
I can undertand that starting from top and going down selecting the max you find is "sortsighted" and may not be the overall max.
但是，为什么是自下而上去顶什么更好的办法？
在我看来，它同样的问题受到影响。
But why is the approach of going from bottom to top any better?
It seems to me it suffers from the same problem.
例如在我们将获得例如三角形（从底部开始）：
9 + 6 + 4 + 3 = 22℃ 23
For example in the triangle in the example we would get (starting from bottom):
9+6+4+3=22 < 23
那么，为什么从下往上开始？
So why start from bottom-up?
推荐答案
这是一种叫做动态规划。
It's something called dynamic programming.
您有这样的三角：
3
7 4
2 4 6
8 5 9 3
当你从底部移动到顶部，你可以计算出在最后一次迭代的最佳选择。
在这种情况下你把最后一行 8 5 9 3 键，除了previous线最大限度地总和。
When you move from the bottom to the top, you can calculate the best choices on last iteration.
In this case you take the last row 8 5 9 3 and maximize sum in addition to previous line.
迭代1：
假设你是在最后1 一步。
Iteration 1:
Assume that you are on last-1 step.
您有一行 2 4 6 让迭代就可以了。
You have line 2 4 6 let iterate on it.
从2 ，你可以去任何 8 或5，所以 8 是更好的（最大化你3结果），所以你计算第一笔8 + 2 = 10
From 2, you can go to either 8 or 5, so 8 is better (maximize you result from 3) so you calculate first sum 8 + 2 = 10
从4 ，你可以去5或 9 ，所以 9 是更好的（最大化你个结果），所以你算算第二个和9 + 4 = 13
From 4, you can go to either 5 or 9, so 9 is better (maximize you result from 4) so you calculate second sum 9 + 4 = 13
从6 ，你可以去任何 9 或3，因此 9 是最好再（最大限度地从6结果），所以你计算第三总和9 + 6 = 15
From 6, you can go to either 9 or 3, so 9 is better again (maximize you result from 6) so you calculate third sum 9 + 6 = 15
这是第一次迭代的结束和你有款项 10 13 15 。
This is the end of first iteration and you got the line of sums 10 13 15.
低维的现在，你已经得到了三角：
Now you've got triangle of lower dimension:
3
7 4
10 13 15
现在下去，直到你得到一个值，而这正是23。
Now go on until you get one value, which is exactly 23.
这篇关于欧拉项目＃18方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
