<p>这个问题不需要复杂的树搜索。答案可以在单个过程中迭代计算</p>
<p>下面是一个简单的解决方案,它从上到下、从左到右遍历矩阵的单元格,累加总和,并根据上面和左边单元格的计算值选择最小的一个。第一行和第一列是无条件求和,因为没有备用路径可通过</p>
<pre><code>from itertools import accumulate
def minSumPath(M):
R = list(accumulate(M[0]))
for row,values in enumerate(M[1:],1):
R = [*accumulate((R[0]+values[0],*zip(R[1:],values[1:])),
lambda left,rv:min(left,rv[0])+rv[1])]
return R[-1]
M = [ [131, 673, 234, 103, 18],
[201, 96, 342, 965, 150],
[630, 803, 746, 422, 111],
[537, 699, 497, 121, 956],
[805, 732, 524, 37, 331]]
print(minSumPath(M)) # 2427
</code></pre>
<p>随着循环的进行,R保持到前一行中每个位置的最小和路径。在上述示例中,R将按如下方式进行:</p>
<pre><code>[131, 804, 1038, 1141, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, 1420]
[1499, 1930, 2013, 2059, 2376]
[2304, 2662, 2537, 2096, 2427]
</code></pre>
<p>最后一行的最后一个值就是答案</p>
<p><em>注意,这种方法可以很容易地调整为使用行迭代器作为输入。这样,它将非常节省内存,因为它只需要保存2行数据即可处理输入文件</em></p>
<p>您还可以使用一种简单的递归方法,通过计算右下角单元格左上方单元格的和路径来获得结果。即使使用记忆,这也比上面的迭代解决方案慢60倍。这是一种有趣的概念方法:</p>
<pre><code>from functools import lru_cache
def minSumPath(M):
@lru_cache() # needs hashable (tuple) parameters
def minSumPathT(T):
if 1 in map(len,(T,T[0])): return sum(map(sum,T)) # single row or column
fromAbove = minSumPathT(T[:-1])
fromLeft = minSumPathT(tuple(row[:-1] for row in T))
return T[-1][-1] + min(fromAbove,fromLeft)
return minSumPathT(tuple(map(tuple,M)))
</code></pre>