帕斯卡三角形最大路径

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