试图理解我在python中找到的三角形最大路径和的代码是如何工作的

Question

以一个三角形为例，格式为嵌套列表。 e、 g

t =  [[5],[3, 6],[8, 14, 7],[4, 9, 2, 0],[9, 11, 5, 2, 9],[1, 3, 8, 5, 3, 2]]

并将路径定义为三角形每行元素的总和， 向下移动行时向左或向右移动1。或者用python 第二个索引要么保持不变，要么加1

a_path = [t[0][0],[t[1][1]],t[2][1],t[3][1],t[4][2],t[5][3]] = [5, 6, 14, 9, 5,5] is valid
not_a_path = [t[0][0],[t[1][0]],t[2][2],t[3][1],t[4][0],t[5][4]] = [5, 3, 7, 9, 9, 3] is not valid

对于像这个例子一样小的三角形，这显然可以通过蛮力来实现。 我写了一个这样的函数，对于一个20行的三角形，大约需要1分钟。 我需要一个函数，可以这样做的100行三角形。 我在https://rosettacode.org/wiki/Maximum_triangle_path_sum#zkl上发现了这段代码，它与我尝试过的小三角形的糟糕函数输出的所有结果一致，并且在控制台中使用%的时间，它可以在0ns内相对快速地完成100行三角形

def maxPathSum(rows):
    return reduce(
        lambda xs, ys: [
            a + max(b, c) for (a, b, c) in zip(ys, xs, xs[1:])
        ],
        reversed(rows[:-1]), rows[-1]
    )

所以我开始做一些这方面的工作，使用打印语句和控制台来了解它在做什么。我得到reversed(rows[:-1]), rows[-1]正在反转三角形，这样我们就可以从最后一行的所有可能的最终值，通过它们可能的路径之和，迭代到该值，并且作为a，b，c迭代：a是底行的一个数字，b是底行的第二个，c是底行的第三个。当它们迭代时，我认为a + max(b,c)似乎与b或c上的最大数相加，但当我试图在控制台中找到两个列表或嵌套列表的最大值时，返回的列表似乎完全是任意的

ys = t[-1]
xs = list(reversed(t[:-1]))
for (a, b, c) in zip(ys, xs, xs[1:]):
    print(b)
    print(c)
    print(max(b,c))
    print("")

印刷品

[9, 11, 5, 2, 9]
[4, 9, 2, 0]
[9, 11, 5, 2, 9]

[4, 9, 2, 0]
[8, 14, 7]
[8, 14, 7]

[8, 14, 7]
[3, 6]
[8, 14, 7]

[3, 6]
[5]
[5]

如果max（b，c）返回包含max（max（b），max（c））的列表，那么b=[3,6]，c=[5]将返回b，所以不是这样。如果max（b，c）返回的列表的最大和max（sum（b），sum（c）），那么同一个例子与之相矛盾。它不会返回包含最小值或具有最大平均值的列表，因此我唯一的猜测是，我设置xs = list(reversed(t[:-1]))的事实就是问题所在，如果它是lambda函数中的迭代器，而不是控制台中的迭代器，那么它可以正常工作

同样试图找到a + max (b,c)也会给我这个错误，这是有道理的

TypeError: unsupported operand type(s) for +: 'int' and 'list'

我最好的猜测是，xs作为列表的不同定义是问题所在。如果是真的，我想知道这一切在lambda函数中作为迭代器的上下文中是如何工作的。我想我明白了reduce（）和zip（）所做的事情，所以最让我困惑的是lambda函数

提前谢谢你的帮助

Answer 1

我们可以通过在第二个要减少的参数中包含所有行来简化表达式—没有理由将最后一行作为reduce的第三个参数（起始值）传递

然后，为变量指定有意义的名称真的很有帮助，而原始代码却没有做到这一点

因此，这变成：

from functools import reduce

def maxPathSum(rows):
    return reduce(
        lambda sums, upper_row: [cell + max(sum_left, sum_right) 
                                 for (cell, sum_left, sum_right) 
                                 in zip(upper_row, sums, sums[1:])],
        reversed(rows)
    )

在第一次迭代中，sums将是最后一行，upper_row将是它上面的一行

lambda将通过将上一行的每个值与其左侧或右侧的最大值sums相加来计算可能的最佳和

它用总和（最后一个总和将不被使用，因为有一个太多），将上一行的总和压缩，并将总和移动一个值。因此，zip将为我们提供一个三元组（从上行（cell）的值，从下到左（sum_left）的和，从下到右（sum_right）。此时最好的和是我们的当前单元格+这些和中最大的一个

lambda返回这一新行总和，它将在下一次迭代中用作reduce（sums）的第一个参数，而upper_row将成为reversed(rows)中的下一行

最后，reduce返回最后一行总和，其中只包含一个值，即我们的最佳总和：

[53]

Answer 2

您可以拼写lambda函数，以便打印。这有助于你理解吗

t =  [[5],[3, 6],[8, 14, 7],[4, 9, 2, 0],[9, 11, 5, 2, 9],[1, 3, 8, 5, 3, 2]]
def g( xs, ys):
    ans=[a + max(b, c) for (a, b, c) in zip(ys, xs, xs[1:])]
    print(ans)
    return ans
def maxPathSum(rows):
    return reduce(
        g,
        reversed(rows[:-1]), rows[-1]
    )
maxPathSum(t)