数字金字塔

写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。如

        动态规划思想，以farray[i][j]作为i,j位置处最大和，它来源于farray[i-1][j-1]、farray[i-1][j]的最大值。

def maxsum(carray):

    farray=[ [0]*len(var) for var in carray ]

    farray[0][0]=carray[0][0]

    length=len(carray)

    for i in range(1,length):

        for j in range(i+1):

                temp=-float('inf')

                for k in range(j-1,j+1):

                    if k==i:

                        temp=farray[i-1][j-1]      #左上角

                    elif k==0:

                        temp=farray[i-1][k]      #上方

                    else:

                        temp=max(temp,farray[i-1][k])    #上方和左上角最大值

                farray[i][j]=carray[i][j]+temp

    return farray

测试用例

>>> carray=[[7],[3,2],[8,1,0],[2,7,4,4],[4,5,2,6,5]]

>>> maxsum(carray)

[[7], [10, 9], [18, 11, 9], [20, 25, 15, 13], [24, 30, 27, 21, 18]]

>>>

>>> carray=[[13],[11,8],[12,7,26],[6,14,15,8],[12,7,13,24,11]]

>>> maxsum(carray)

[[13], [24, 21], [36, 31, 47], [42, 50, 62, 55], [54, 57, 75, 86, 66]]

>>>