###python版本
import numpy as np
class triangle_dynatic():
def main(self,data):
#data塔的原始数据，dp存储动态数据
dp = np.zeros(np.array(data).shape)
#n为行数，在这里相当于塔数
n,m = np.array(data).shape
#初始化dp
#下面这个循环相当于把data的最后一行付给了dp的最后一行，就是从最后一行向上递归
for i in range(n):
dp[n-1][i] = data[n-1][i]
print(dp)
#第一个循环从最底层往上，第二层循环从左向右，在这里从第四层，就是倒数第二层开始向上进行动态规划
for i in range(n-2,-1,-1):
for j in range(i+1):
temp_max = max(dp[i+1][j],dp[i+1][j+1])
dp[i][j] = temp_max+data[i][j]
#打印最终结果
print('最大的路径和为：\n%d'%dp[0][0])
#首先输出塔顶元素
print('最大路径：\n->%d'%data[0][0])
j = 0
#依次输出2/3/4/5层的所选路径
for i in range(1,n):
node_value = dp[i-1][j]-data[i-1][j]
#如果node_value == dp[i][j]则说明下一步应该是data[i][j]；如果node_value == dp[i][j + 1]则说明下一步应该是data[i][j + 1]
if node_value == dp[i][j+1]:
j = j+1
print('->%d'%data[i][j])
data = [[9,0,0,0,0],[12,15,0,0,0],[10,6,8,0,0],[2,18,9,5,0],[19,7,10,4,16]]
triangle_dynatic().main(data)
