博客

//评测题目: 给定一个三角形 triangle ，找出自顶向下的最小路径和。

//每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
//也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
//示例 1：

//输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
//输出：11
//解释：如下面简图所示：
//   2
//  3 4
// 6 5 7
//4 1 8 3
//自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）

三种实现方法

# 逻辑实现
def minsum1(triangle):
    n = len(triangle)
    if n == 0:
        return 0
    if n == 1:
        return triangle[0][0]
    path = [ [float("inf")]*(i+1) for i in range(n)]

    for i in range(n):
        if i == 0:
            path[i][0] = triangle[i][0]
        else:
            path[i][0] = path[i-1][0] + triangle[i][0]

    for i in range(1,n):
        for j in range(1,i):
            path[i][j] = min(path[i-1][j],path[i-1][j-1]) + triangle[i][j]

    return min(path[n-1])

# 递归实现
# 参考：　https://blog.csdn.net/ailaojie/article/details/83014821
def minsum2(triangle,i=0,j=0):
    if len(triangle) == 0:
        return 0
    elif i == len(triangle)-1:
        return triangle[i][j]
    else:
        return min(minsum2(triangle,i+1,j),minsum2(triangle,i+1,j+1))+triangle[i][j]


# 从底向上
def minsum3(triangle):
    n = len(triangle)
    if n == 0:
        return 0
    for i in range(n-2,-1,-1):
        for j in range(i+1):
            triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1])
    return triangle[0][0]

if __name__ == "__main__":
    triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    rst1 = minsum1(triangle)
    rst2 = minsum2(triangle)
    rst3 = minsum3(triangle)
    print(rst1,rst2,rst3)