018. 最大和的路径(maximum path sum I)

从以下这个三角形的顶部开始,向相邻的下一行的数字移动,经过之数所能得到的最大的和为23,即:\(3+7+4+9=23\)

$$ 3\\ 7\quad4\\ 2\quad4\quad6\\ 8\quad5\quad9\quad3 $$
对于以下三角形(见数据文件ep18.txt),求期从上到下所有路径中最大的和。【注:由于总共只有16384条路径,因此可以尝试每条路径并求最大值。然而,问题67与此问题类似但有三角形共有100行,从而无法用暴力枚举方法解决,这需要一个聪明的方法。】

分析:这是一道经典的动态规划问题,为求三角形从上到下的最大和,先从最下一行开始倒推,即:

$$ max(8+2,5+2)=10,max(5+4,9+4)=13,max(9+6,3+6)=15 $$

这样可以将最下二行合为一行,即:

$$ 3\\ 7\quad4\\ 10\quad13\quad15 $$

依次类推,可以继续倒推出:

$$ max(10+7,13+7)=20,max(13+4,15+4)=19 $$

即:

$$ 3\\ 20\quad19 $$

容易得到23是最大值,而路径也是题目中所给出的路径。对于题目中给出的三角形,与之类似可以得出答案。代码中同时实现了从上而下和从下而上的两种动态规划方法:

with open('data/ep18.txt') as f:
    table = [list(map(int,s.split())) for s in f.readlines()]

# approach 1: bottom-up method, time cost = 62.1 µs ± 5.71 µs

def main():
    for row in range(len(table)-1, 0, -1):
        for col in range(0, row):
            table[row-1][col] += max(table[row][col], table[row][col+1])
    return table[0][0]

# approach 2: top-down method, time cost = 131 ns ± 8.97 ns

from functools import lru_cache

@lru_cache(maxsize=128)
def mps(r=0,c=0):
    if r == len(table)-2:
        return table[r][c] + max(table[r+1][c],table[r+1][c+1])
    else:
        return table[r][c] + max(mps(r+1,c),mps(r+1,c+1))