樹中最大的總和

Question

我在三角形中試圖找到最大總和的路徑，我發現這個代碼是http://rosettacode.org/wiki/Maximum_triangle_path_sum#Python。現在，我想完全理解的代碼做什麼，但我不能找出這行代碼究竟：

tri.append([max(t0[i], t0[i+1]) + t for i,t in enumerate(t1)]) 

我知道這東西追加這是關係到t0的最大值[我]和T0 [I + 1]，但我不知道是什麼最後的部分是指：

+ t for i,t in enumerate(t1)]) 

我希望有人能幫助我，或翻譯這對一個正常的循環。 在此先感謝

Answer 1

讓我們假設三角形存儲在矩陣中，並讓n是最後一行三角形中的元素數。讓我們這個三角爲例：

1 
2 3 
4 5 6 

由於最後一排有3個要素，我們將創建3×3的矩陣和矩陣初始化爲零。我們的矩陣將類似於以下內容：

1 0 0 
2 3 0 
4 5 6 

我們只能將本元以下或對角right.So，我們可以在第一行從任何一點開始，遍歷直至最後一行。獲得所有路徑的總和並獲取這些路徑的最大值。

n = 3 
def f(x,y): 
    if(x >= n or y >= n): 
     return 0 
    return max(f(x+1,y),f(x+1,y+1)) + a[x][y] #take the maximum of both the paths 

a = [[0 for i in range(n)] for i in range(n)] 
a[0][0] = 1 
a[1][0] = 2 
a[1][1] = 3 
a[2][0] = 4 
a[2][1] = 5 
a[2][2] = 6 
maximum = 0 
for i in range(0,n): 
    maximum = max(maximum,f(0,i)) #we can start from any of the cell in the first row 
print maximum 

我們將獲得10作爲最高金額，如果我們按照這種情況下，路徑1 3 6。