动态规划三角形最小路径和

动态规划求解三角形最小路径和问题，可以使用自底向上的方法，从最底层开始逐层向上求解，最终得到最小路径和。

具体做法如下：

1. 定义状态：设 $dp[i][j]$ 表示从三角形的第 $i$ 行第 $j$ 列出发到达三角形底部的最小路径和。

2. 初始化状态：$dp[n][j] = triangle[n][j]$，即三角形最后一行的值就是对应位置上的值。

3. 状态转移：对于每个位置 $(i, j)$，从它的下一层邻居中选择一个路径和最小的那个，加上自己的值，即可得到从当前位置到达底部的最小路径和，即 $dp[i][j] = triangle[i][j] + \min(dp[i+1][j], dp[i+1][j+1])$。

4. 最终解：最终的解即为 $dp[1][1]$，即从三角形顶部到达底部的最小路径和。

代码实现如下：

def minimumTotal(triangle):
    n = len(triangle)
    dp = triangle[-1] # 初始化为最后一行的值
    for i in range(n-2, -1, -1): # 从倒数第二行开始逐层向上
        for j in range(i+1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    return dp[0]

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

相关问题

动态规划算法求三角形最小路径问题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` 是一个二维列表，表示三角形的每一行。函数返回三角形从顶部到底部的最小路径和。

动态规划算法求三角形最小路径问题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`，即为三角形从顶到底的最小路径和。