欧拉项目＃18方法
我正在研究欧拉项目。 具体＃18。
总结起来，这个想法是从三angular形中find最大的path：
3 7 4 2 4 6 8 5 9 3 3 + 7 + 4 + 9 = 23。
为此，大多数人表示，这是通过自上而下的正确解决，而不是使用从上到下“贪婪”的algorithm。
我可以承认，从最高层开始往下select你发现的最大值是“有目共睹的”，可能不是整体最大值。
但为什么从底部到顶部的方法更好？
在我看来，它遭受同样的问题。
例如在例子中的三angular形中，我们将得到（从底部开始）：
9 + 6 + 4 + 3 = 22 <23
那么为什么从下往上开始呢？
这就是所谓的dynamic编程。
你有这样的三angular形：
3 7 4 2 4 6 8 5 9 3
当您从底部移动到顶部时，您可以计算上次迭代的最佳select。 在这种情况下，除了上一行之外，还要取最后一行8 5 9 3并使总和最大。
迭代1：假设你在last-1一步。
你有第2 4 6行2 4 6 ，让我们迭代它。
从2 ，你可以去8或5，所以8更好（从2最大化你的结果），所以你计算第一个和8 + 2 = 10。
从4 ，你可以去5或9 ，所以9更好（从4最大化你的结果），所以你计算第二个和9 + 4 = 13。
从6 ，你可以去9或3，所以9再次更好（从6最大化你的结果），所以你计算第三个和9 + 6 = 15。
这是第一次迭代的结束，你得到了总和10 13 15 。
现在你已经有了更低维度的三angular形：
3 7 4 10 13 15
现在继续，直到你得到一个值，这正好是23。
区别不在于自上而下和自下而上。 贪婪和“边界”方法的区别。
一个贪婪的algorithm不一定会帮助你，因为如果树的最好的部分不可及，你不能恢复。 例如：一个贪婪的algorithm会从上到下selectpath1-3。 它会完全错过9。
1 2 3 9 1 1
为了find真正的最大值，你必须基本遍历几乎所有的path。
如下所述，自下而上的方法没有这个问题。 它至多检查n *（n-1）个path：每个元素2个。 然而，将其称为“自下而上”的做法是误导性的。
为什么？ 因为有一种自上而下的方法是等价的。 其实质是，对边疆后面所有树木来说，你有一种“边疆”，效果最好。 无论你是前移还是后移都是次要的。 对于上面的例子中的自顶向下的方法，你要为每一行计算每个元素的总和和它上面两个最好的总和的最大值：
1 3 4 12 5 5
在自下而上的方法中，您可以计算每个元素的总和以及下面两个最佳总数的最大值。 相反的顺序：
9 1 1 11 4 12
在这些自上而下和自下而上的方法中，大约有同样的工作。
使用你的例子，“自下而上”的方法是：
检查底部行，你可以从每个元素获得最多
8,5,9,3
检查下一行，你可以从每个元素得到的最多（取决于你是从左边还是右边）：
2 + max（8,5），4 + max（5,9），6 + max（9,3）= 10,13,15
所以这很好。 我们已经消除了两行，把它们压在一起，用一行代替它们，从而减less了问题的发生
3 7 4 10 13 15
显然我们可以继续重复这一点。 检查下一行，你可以从每个元素获得最多的
7 +最大（10,13），4 +最大（13,15）= 20,19
所以从顶端，你可以得到的最多
3 +最大（20,19）= 23
QED。
其实你不需要自下而上 你也可以自上而下开始，只要你做得好。
在金字塔的每个层次上发生什么事情都可以很好地说明它的运作方式。 道路必然要跨越每个层面。
x xx xhx xyyx xyyyx
我们说这是h 。 从允许path的定义来看，path只能跟踪到y标记的地方，这就形成了一个类似于原始的问题 – 如果我们通过y sfind最大path，整个三angular形的最大path实际上通过h ，那么肯定会沿着ys中的最大path（如果不是的话，你可以切换较小三angular形中的path部分并获得总体上更好的path）。
所以，如果你构造自上而下的algorithm，从当前节点向下计算最大path，你会得到正确的结果（即最大path值，从中你可以很容易地得到path本身）。
现在，这需要O（N）（N表示数字的数量），因为对于每个地方，您只需考虑两条path并使用来自较低级别的预先计算的值。
几乎相同的algorithm可以实现自顶向下，从顶部开始并递减，只要记忆结果即可。
best_length(node) { if(node is terminal) return value(node) int m = 0 for(next : lower neighbors of node) m = max(best_length(next), m) return m + value(node); }
这种自顶向下的另一种可能性就是逆转计算。 您从顶部开始，为每个节点考虑其上邻居，并获得从该节点的顶部结束的path长度（而不是从该节点到底部行的path）。 最后，你从下面一行收集数据，你就完成了。
采取自下而上的方法消除path，而自上而下只增加潜在的path。
因为您可以更快地消除不良path，所以先做广度优先search就成为最佳解决scheme。 在任何一个方向进行深度优先search都是错误的（如你所示），而且速度慢。
这是一个可以用图论解决的问题。 对于每个点，您只能前往它的两个“子”（它下面的左右节点）。 对于所有的叶子节点（最下面的一行），都包含一个“端节点”的path（零成本）。
你想要最大的数字，而这又是最长的path。
要做到这一点，你需要实现一个BFS（通常是最短pathalgorithm），而不是让父节点和子节点之间的权重为子节点的值，而是使其成为子节点值的加法逆。
你不能在这里很容易地使用Dijkstra，因为Dijkstra只适用于非负的path。
BFS的运行时间为O（| E | + | V |）。
在三angular形中有1 + 2 + 3 + 4 + 5 + .. + n =（1/2） （n） （n-1）个节点
这意味着有（n） （n-1）条path，加上最后一个节点连接的（n）
总数：（1/2） （3n ^ 2 -n）其中n是行数。
由于行数很less，所以也可以使用recursion来计算最大的总和：
import sys def max_sum(i,j): if i==14: return a[i][j] return a[i][j]+max(max_sum(i+1,j),max_sum(i+1,j+1)) a=[] for i in range(15): b=list(map(int,sys.stdin.readline().split())) a.append(b) print(max_sum(0,0))
对于问题67 – （最大path总和II），您可以使用memoisation：
import sys d={} def max_sum(i,j): if (i,j) in d: return d[(i,j)] if i==99: return a[i][j] d[(i,j)]=a[i][j]+max(max_sum(i+1,j),max_sum(i+1,j+1)) return d[(i,j)] a=[] for i in range(100): b=list(map(int,sys.stdin.readline().split())) a.append(b) print(max_sum(0,0))
这里是一个完整的答案：
#include <iostream> using namespace std; int main() { int sum1,sum2; int A[4][4] = {{3,0,0,0},{7,4,0,0},{3,4,6,0},{8,5,9,3}}; for(int i=2;i>=0;i--){ for(int j=0;j<4;j++){ sum1=A[i][j]+A[i+1][j]; sum2=A[i][j]+A[i+1][j+1]; if(sum1>sum2){ A[i][j]=sum1; } else{ A[i][j]=sum2; } } } cout<<A[0][0]<<endl; }
