动态规划-数字三角形V2

数字三角形V2:
上一种方法计算会有大量的重复计算，如果数组过大，会超时。
7 1
3 1 8 1
8 1 1 2 0 1
2 1 7 3 4 3 4 1
4 1 5 4 2 6 6 4 5 1
如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为 2 n ,
对于 n = 100 行，肯定超时。
改进思路：如果每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，
则可免去重复计算。那么可以用O(n 2 )时间完成计算。因为三角形的数字总数是 n(n+1)/2

python算法实现：

 1 # 为了方便计算，数组的值从1，1位置开始存储
 2 d = [[0] * 101 for j in range(101)]
 3 maxD = [[-1] * 101 for j in range(101)]
 4 
 5 
 6 def MaxSum(i, j, rows):
 7     if (maxD[i][j] != -1):
 8         return maxD[i][j]
 9     if i == rows:
10         return d[i][j]
11     else:
12         x = MaxSum(i + 1, j, rows)
13         y = MaxSum(i + 1, j + 1, rows)
14         maxD[i][j] = max(x, y) + d[i][j]
15     return maxD[i][j]
16 
17 
18 def main():
19     global d
20     lines = int(input("请输入行数："))
21     for i in range(lines):
22         line = input().split()
23         for j in range(i + 1):
24             d[i + 1][j + 1] = int(line[j])
25     # print(d)
26     maxPath = MaxSum(1, 1, lines)
27     print("最大路径值为：%d" % maxPath)
28 
29 
30 if __name__ == "__main__":
31     main()