python - 欧拉 #18 与 Python

Question

我正在尝试解决项目欧拉问题 18。 http://projecteuler.net/problem=18 我尝试了一个贪心算法，python 从三角形底部开始工作。然后我向上移动一排并使用贪婪算法找到最大的路线并尝试连接最大的路线但它不起作用。您是否有任何提示可以让我走上正确的轨道，而不会给出问题的解决方案。

这是功能：

def greedy(i):
    if i%15==0:
        a=[(b[i-15],i-15),(b[i-14],i-14)]
        a=sorted(a)
        a=a[-1]
    else:
        a=[(b[i-15],i-15),(b[i-16],i-16),(b[i-14],i-14)]
        a=sorted(a)
        a=a[-1]
    return a

干杯

Answer 1

你听说过动态规划吗？

考虑这个问题。什么使路线最好？最后一步和上一步之间有什么关系吗？另外，看看这个贪心算法没有给你正确答案的三角形：

      1
    2   3
  9   1   2
1   1   2   4