求解释Python实现三角形最大路径和的代码工作逻辑及调试异常原因
三角形最大路径和实现逻辑拆解
基础规则定义
- 测试用三角形以嵌套列表存储,示例:
t = [[5],[3, 6],[8, 14, 7],[4, 9, 2, 0],[9, 11, 5, 2, 9],[1, 3, 8, 5, 3, 2]] - 合法路径规则:逐行从三角形中选一个元素,向下移动时索引保持不变或加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] - 非法路径示例:
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](移动时索引跳变)
- 合法路径示例:
- 暴力法局限:小尺寸三角形可通过暴力枚举求解最大路径和,但20行规模的三角形暴力计算需约1分钟,完全无法满足100行规模三角形的计算效率需求。
高效实现代码
该实现对小三角形的计算结果和暴力法完全一致,100行规模三角形的计算耗时极短,性能远优于暴力法:
from functools import reduce 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] )
调试遇到的问题
已知核心设计思路是从最后一行向上倒序累加路径和,对reduce()和zip()的作用有基础认知,但对lambda部分的实现逻辑存在疑惑:
- 手动调试时直接把xs赋值为
list(reversed(t[:-1])),遍历zip(ys, xs, xs[1:])得到的b、c均为列表,max(b,c)返回结果不符合预期 - 计算
a + max(b,c)时触发类型错误:TypeError: unsupported operand type(s) for +: 'int' and 'list' - 最初猜测异常是手动将xs转为列表,和原代码中reduce传入的迭代器形式有差异,希望厘清函数完整工作逻辑,尤其是lambda部分的实现原理
逐逻辑拆解
reduce参数的实际作用
reduce()的三个入参分别为迭代用的lambda函数、待迭代的输入序列、初始累积值,本函数的执行流完全围绕三个参数展开:
- 初始状态:累积值
acc= 三角形最后一行rows[-1],即最开始的xs就是三角形最底层的原始行列表 - 待迭代输入序列为
reversed(rows[:-1]),即把三角形除最后一行外的部分,从倒数第二行开始向上逐行遍历,每取到的一行作为单轮迭代的ys - 每轮迭代传入lambda的两个参数角色完全固定:
- 第一个参数xs:当前层计算得到的「下层最大路径和列表」,长度永远比ys多1
- 第二个参数ys:原三角形向上遍历到的当前行原始元素,长度永远比xs少1
lambda核心逻辑演示
拿示例三角形 t = [[5],[3, 6],[8, 14, 7],[4, 9, 2, 0],[9, 11, 5, 2, 9],[1, 3, 8, 5, 3, 2]]做逐轮计算演示:
- 初始xs = 最后一行原始值:
[1, 3, 8, 5, 3, 2] - 第一次迭代取到ys = 倒数第二行原始值:
[9, 11, 5, 2, 9]- 执行
zip(ys, xs, xs[1:]),三个参与zip的对象分别是:当前行ys、已经算好的下层路径和xs、偏移1位的下层路径和xs[1:] - zip后得到的每一组三元组为:
(9, 1, 3)、(11, 3, 8)、(5, 8, 5)、(2, 5, 3)、(9, 3, 2) - 每组计算
a + max(b,c):a是当前行的原始元素,b和c是下一层相邻两个位置的最大路径和,取较大值累加得到当前位置到三角形底部的最大路径和 - 计算得到新的xs值:
[12, 19, 13, 5, 11],即从倒数第二行每个元素出发到底部的最大路径和
- 执行
- 第二次迭代取到ys = 倒数第三行原始值:
[4, 9, 2, 0],重复zip计算得到新的xs值:[23, 28, 15, 11] - 逐行向上重复计算,直到处理完第一行,最终xs中剩下的唯一元素,就是整个三角形的最大路径和。
调试错误的根本原因
手动调试时把xs赋值为list(reversed(t[:-1])),完全颠倒了xs和ys的参数角色:
- 原代码中的xs永远是计算得到的下层路径和,不是原三角形的原始行
- ys才是从原三角形逐行向上取的原始元素
- 当手动把xs设为原三角形的倒序行列表时,xs和ys都是普通原始行,不满足“xs长度比ys多1、xs是下层路径和”的前置条件,zip遍历得到的b、c自然是列表级别的对象,既不符合max比较的预期场景,也会触发整数和列表相加的类型错误。这个问题和迭代器/列表的形式差异无关,纯粹是参数角色混淆导致的。
内容的提问来源于stack exchange,提问作者John
相关产品推荐
相关产品推荐

