学步园

def Triangel(a,n):
    #d[i][j]即为状态，从格子(i,j)出发能得到的最大值
    d=[[0 for col in range(n+1)] for row in range(n+1)] 
    for i in range(n+1):
        d[n][i]=a[n][i]
    #双重循环自下而上计算最大和
    i=n-1
    while(i>=0):
        for j in range(i+1):
            d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]) #状态转移方程
        i-=1
    print(d[0][0])


#test
a=[[1],[3,2],[4,10,1],[4,3,2,20]]   #数字三角形数据
n=3     #层数,从0开始计数
Triangel(a,n)