动态规划算法求三角形最小路径问题python完整代码

下面是Python实现的动态规划算法求解三角形最小路径问题的完整代码：

triangle = [
    [2],
    [3,4],
    [6,5,7],
    [4,1,8,3]
]

n = len(triangle)
dp = [[0] * n for _ in range(n)]

# 初始化dp数组最后一行
for i in range(n):
    dp[n-1][i] = triangle[n-1][i]

# 从倒数第二行开始递推
for i in range(n-2, -1, -1):
    for j in range(i+1):
        dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])

# 结果为dp[0][0]
print(dp[0][0])

输出结果为 `11`，即为三角形从顶到底的最小路径和。

相关问题

动态规划算法求三角形最小路径问题python代码

以下是 Python 实现的动态规划算法求三角形最小路径问题的代码：

def minimumTotal(triangle):
    """
    :type triangle: List[List[int]]
    :rtype: int
    """
    # 初始化最后一行
    dp = triangle[-1]
    
    # 从倒数第二行开始
    for i in range(len(triangle) - 2, -1, -1):
        # 遍历当前行
        for j in range(len(triangle[i])):
            # 选择下一行中相邻的两个数中的较小值，并加上当前位置的值
            dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
    
    # 返回最终结果
    return dp[0]

其中，`triangle` 是一个二维列表，表示三角形的每一行。函数返回三角形从顶部到底部的最小路径和。