三角形最短路径和

#############################################################
# 思路：自顶向下计算每一行距离的所有可能，并用一个列表存放最下面一行的所有距离，最后找到这个列表里最小的值并返回


#创建三角形
def create_triang():
    Trag = [[2],
            [3,4],
            [6,5,7],
            [4,1,8,3]
            ]
    return Trag

def Cnm(n,m):   #定义组合数运算
    if m == 0:
        return 1
    elif n == 0:
        return 1
    elif m == n:
        return 1
    else:
        a = n
        b = 1
        c = n
        for i in range(1,m):
            c = c - 1
            a = a * c
        for i in range(1,m+1):
            b = b * i
    return a/b

#计算距离
def distance(Trag):
    distance = [Trag[0][0]]
    if len(Trag) <= 1:               #如果整个三角形长度小于等于1则返回第一行中所有元素中最小的值
        distance = min(Trag[0])
    else:
        for i in range(len(Trag)-1):    #否则，从 0 到列表长度减一进行遍历运算
            m = 0
            for j in range(len(Trag[i])): #对二维数组内的每个子数组进行遍历
                for c in range(int(Cnm(i,j))): #每一个原来的子数组对应要加的距离个数为Cij个，逐个相加并放入distance列表中
                    distance = distance + [distance[m+c] + Trag[i+1][j],distance[m+c]+Trag[i+1][j+1]]
                m = m + c + 1
            for k in range(2**i):#从1到n，对应的每行距离为2**（n-1) 删除上一行的所有距离参数，避免影响最后求最小值
                distance.pop(0)

    return distance



if __name__ == '__main__':
    Trag = create_triang()
    nearest_D = min(distance(Trag))
    print(nearest_D)