歐拉＃18與Python

Question

我想解決project euler problem 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

你聽說過的Dynamic Programming？

考慮這個問題。什麼使路線最好？最後一步和以前的步驟之間有沒有關係？另外，看看這個三角形的貪婪算法並不能給你正確的答案：

 1 
    2 3 
    9 1 2 
1 1 2 4