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

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

具体做法如下：

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)$。

相关问题

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

### 使用动态规划计算三角形最小路径和

#### 算法思路
对于给定的三角形数组，可以通过自底向上或自顶向下的方式应用动态规划来找到最小路径和。这里采用自底向上的方法，因为这种方法不需要额外的空间用于存储整个二维表。

在处理过程中，`dp[i][j]` 表示从位置 `(i,j)` 到达底部所需的最小路径和。最终的结果保存于 `dp[0][0]` 中[^4]。

为了节省空间复杂度，可以在原地修改输入数据结构中的数值作为临时记录使用的 DP table。具体来说，在遍历每一层节点时更新其上方两层对应位置处的数据；当完成最后一轮迭代之后即可得到所求答案。

#### Python 实现代码
下面是具体的 Python 实现：

def minimumTotal(triangle):
    n = len(triangle)

    # 如果只有一个元素，则直接返回该元素值
    if n == 1:
        return triangle[0][0]

    # 自底向上填充DP Table
    for i in range(n - 2, -1, -1):  
        for j in range(len(triangle[i])):
            triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])

    # 返回顶部元素即为最短路径总和
    return triangle[0][0]

此函数接收一个列表形式表示的三角形并返回其中一条由顶端到底端经过各层不同结点构成的路径长度之和最小者。通过上述过程实现了对题目要求的有效解答[^5]。

针对给出的例子：

     2
    3 4
   6 5 7
  4 1 8 3

按照以上逻辑执行后会得出最优解路径为：2 -> 3 -> 5 -> 1 ，对应的最小路径和为 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` 是一个二维列表，表示三角形的每一行。函数返回三角形从顶部到底部的最小路径和。