帕斯卡三角形最大路径

Question

我正在尝试解决项目 Euler 中的问题 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

给定一个二维列表，它将找到从三角形顶部到底部的最大路径。有人可以解释一下这段代码有什么问题吗？

Answer 1

除此行外的所有内容都已检查：

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

这里其实有两个问题。第一个是它应该是 p 而不是 p + 1。考虑一下，p 的当前值从前一行延续到第一行之后的任何行。所以 p + 1 保证定义明确。实际上，您可以从 1 开始计算总数，从第二行开始迭代，您甚至不需要具备该条件。

第二个问题是次要的，但你不需要每次都计算长度。行的长度始终等于它的 0 索引加一，因此只需与 x 进行比较即可。

这是您的代码在修复后的样子：

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

帕斯卡三角形最大路径

Pascal triangle maximum path

python

arrays

pascals-triangle