回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>以一个三角形为例,格式为嵌套列表。
e、 g</p>
<pre><code>t = [[5],[3, 6],[8, 14, 7],[4, 9, 2, 0],[9, 11, 5, 2, 9],[1, 3, 8, 5, 3, 2]]
</code></pre>
<p>并将路径定义为三角形每行元素的总和,
向下移动行时向左或向右移动1。或者用python
第二个索引要么保持不变,要么加1</p>
<pre><code>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
</code></pre>
<p>对于像这个例子一样小的三角形,这显然可以通过蛮力来实现。
我写了一个这样的函数,对于一个20行的三角形,大约需要1分钟。
我需要一个函数,可以这样做的100行三角形。
我在<a href="https://rosettacode.org/wiki/Maximum_triangle_path_sum#zkl" rel="nofollow noreferrer">https://rosettacode.org/wiki/Maximum_triangle_path_sum#zkl</a>上发现了这段代码,它与我尝试过的小三角形的糟糕函数输出的所有结果一致,并且在控制台中使用%的时间,它可以在0ns内相对快速地完成100行三角形</p>
<pre><code>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]
)
</code></pre>
<p>所以我开始做一些这方面的工作,使用打印语句和控制台来了解它在做什么。我得到<code>reversed(rows[:-1]), rows[-1]</code>正在反转三角形,这样我们就可以从最后一行的所有可能的最终值,通过它们可能的路径之和,迭代到该值,并且作为a,b,c迭代:a是底行的一个数字,b是底行的第二个,c是底行的第三个。当它们迭代时,我认为<code>a + max(b,c)</code>似乎与b或c上的最大数相加,但当我试图在控制台中找到两个列表或嵌套列表的最大值时,返回的列表似乎完全是任意的</p>
<pre><code>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("")
</code></pre>
<p>印刷品</p>
<pre><code>[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]
</code></pre>
<p>如果max(b,c)返回包含max(max(b),max(c))的列表,那么b=[3,6],c=[5]将返回b,所以不是这样。如果max(b,c)返回的列表的最大和max(sum(b),sum(c)),那么同一个例子与之相矛盾。它不会返回包含最小值或具有最大平均值的列表,因此我唯一的猜测是,我设置<code>xs = list(reversed(t[:-1]))</code>的事实就是问题所在,如果它是lambda函数中的迭代器,而不是控制台中的迭代器,那么它可以正常工作</p>
<p>同样试图找到<code>a + max (b,c)</code>也会给我这个错误,这是有道理的</p>
<pre><code>TypeError: unsupported operand type(s) for +: 'int' and 'list'
</code></pre>
<p>我最好的猜测是,xs作为列表的不同定义是问题所在。如果是真的,我想知道这一切在lambda函数中作为迭代器的上下文中是如何工作的。我想我明白了reduce()和zip()所做的事情,所以最让我困惑的是lambda函数</p>
<p>提前谢谢你的帮助</p>