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))