帕斯卡三角形最大路徑

Question

我想解決項目歐拉中的問題18。看到這裏，https://projecteuler.net/problem=18。

def maxpath(triangle): 
    p = 0 
    total = 0 
    for x in range(0,len(triangle)): 
     if p + 1 < len(triangle[x]) - 1: 
      if triangle[x][p+1] > triangle[x][p]: 
       p += 1 
     total += triangle[x][p] 
    return total 

給定一個2維列表，它會找到從三角形頂部到底部的最大路徑。有人可以解釋這段代碼有什麼問題嗎？

Answer 1

一切正常，除了這一行：

if p + 1 < len(triangle[x]) - 1: 

這裏有實際上是兩個問題。第一個是它應該是p而不是p + 1。考慮一下，p的當前值從前一行繼續，對於第一行之後的任何行。所以p + 1保證是明確的。實際上，你可以從1開始你的總數，從第二行開始迭代，你甚至不需要這樣的條件。

第二個問題很小，但不需要每次計算長度。一行的長度總是等於它的0-索引加一，所以只需要與x比較。

這是你的代碼是什麼樣子固定後：產生

23 

---

def maxpath(triangle): 
    p = 0 
    total = 0 
    for x in range(len(triangle)): 
     if p < x and (triangle[x][p + 1] > triangle[x][p]): 
       p += 1 
     total += triangle[x][p] 
    return total 

而現在，

maxpath([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]) # Euler website example 

如果您想進一步優化它（刪除x < p檢查，你可以這樣做：

def maxpath(triangle):  
    p = 0 
    total = triangle[0][0] 
    for x in range(1, len(triangle)): 
     if triangle[x][p + 1] > triangle[x][p]: 
      ... # the rest stays the same