正確的代碼，但錯答:(

Question

我在Python解決Project Euler Problem #18。

我已經成功地解決了給那裏的樣品問題，但解決的主要問題失敗了。但是，代碼是一樣的。

代碼是：？

matrix = [('75', '0'), 
    ('95', '64'), 
    ('17', '47', '82'), 
    ('18', '35', '87', '10'), 
    ('20', '04', '82', '47', '65'), 
    ('19', '01', '23', '75', '03', '34'), 
    ('88', '02', '77', '73', '07', '63', '67'), 
    ('99', '65', '04', '28', '06', '16', '70', '92'), 
    ('41', '41', '26', '56', '83', '40', '80', '70', '33'), 
    ('41', '48', '72', '33', '47', '32', '37', '16', '94', '29'), 
    ('53', '71', '44', '65', '25', '43', '91', '52', '97', '51', '14'), 
    ('70', '11', '33', '28', '77', '73', '17', '78', '39', '68', '17', '57'), 
    ('91', '71', '52', '38', '17', '14', '91', '43', '58', '50', '27', '29', '48'), 
    ('63', '66', '04', '68', '89', '53', '67', '30', '73', '16', '69', '87', '40', '31'), 
    ('04', '62', '98', '27', '23', '09', '70', '98', '73', '93', '38', '53', '60', '04', '23')] 

i = 0 
j = 0 
len = len(matrix) 
sum = 0 

for i in range(0,len): 

    if matrix [i][j] > matrix [i][j + 1]: 
     print matrix [i][j] 
     sum = sum + int(matrix [i][j]) 
    else: 
     print matrix [i][j+1] 
     j = j + 1 
     sum = sum + int(matrix [i][j]) 
print sum 

誰能告訴我在哪裏，我錯了

Answer 1

很抱歉，但您使用的是不正確的算法
您使用的是Greedy Algorithm，但使用的正確算法是Dynamic Programming。主要區別在於貪婪選擇最佳當前選項作爲選擇，而動態編程枚舉每個可能的選項併產生一系列選擇。

沒有哪個解決方案（貪婪），將不能簡單的例子：

0, 
1, 0, 
0, 0, 10 

最好的結果是10，但你的算法將給予1代替。

想一想自己一會兒，然後嘗試尋找關於動態規劃的信息。 Euler項目是一個很棒的地方，當你想出一個解決方案時，感覺非常棒。所以我現在就不多說了。 :)

更新：

但是QUES：通過啓動在低於三角形的頂部和下面的行移動到「鄰近的號碼」。我已經根據這個詞做了我的代碼。對不起打擾，但你能讓我更清楚這個詞嗎？

請注意，實際上2^(n-1)可能會在給定的n級別三角形上出現。在原始問題maximum total意味着所有這些路線中的最大總數。
由於您只在TWO選項中選擇了更好的選項，因此您的代碼無法在ALL路線中找到最大值。

再次更新：在這個問題

其實因爲n=15足夠小，還可以列舉所有2^(n-1)=16384可能的途徑，總結每條路線的總價值，並最終獲得中你得到的最大總。但是，在Problem 67 of Project Euler問題大小n增加到100，並且將不可能枚舉所有2^(n-1)=633825300114114700748351602688路由。

順便說一句，我已經發布了一個鏈接到維基頁面的動態編程，但恐怕這是複雜的閱讀作爲首發。對不起。
不過不用擔心，只是谷歌dynamic programming tutorial，你會得到許多有用的資源，看看:)