分析:这个问题我们在第十八题中的已经使用动态规划的方法解决了,代码可以不加修改的直接使用,只需要把数据文件改成这里的文件就可以了,相关思路大家可以参阅第十八题,这里直接列代码:
with open('data/ep67.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))