LeetCode 题目 120：三角形最小路径和

作者介绍：10年大厂数据\经营分析经验，现任字节跳动数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python，欢迎探讨交流
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
漫画版算法详解
python源码解读
程序员必备的数学知识与应用

题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下一行中与这个结点正下方或者正下方右边的结点。

在这里插入图片描述

方法一：动态规划（自底向上）

解题步骤：

从三角形的最后一行开始，用一个数组 dp 存储到当前行每个元素的最小路径和。
对于三角形的每一行，更新 dp 数组中的每个值，使其等于当前元素加上它下面行中相邻元素的较小者。
最终，dp 数组的第一个元素将包含从顶部到底部的最小路径和。

Python 代码示例

def minimumTotal(triangle):
    dp = triangle[-1]
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

方法一使用动态规划的自底向上方式来计算三角形的最小路径和。我们将通过 ASCII 图形来展示这个方法的工作过程，特别是如何迭代更新从底层到顶层的计算过程。

算法图解

考虑一个具体的三角形：

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

我们从三角形的最后一行开始，并逐行向上更新每个元素的最小路径和。

初始状态

初始化 dp 数组为三角形的最后一行：

dp: [4, 1, 8, 3]

更新到第二行

更新 dp 数组为倒数第二行的每个元素加上其下面行中相邻元素的较小者：

更新过程：
dp[0]: 6 + min(4, 1) = 6 + 1 = 7
dp[1]: 5 + min(1, 8) = 5 + 1 = 6
dp[2]: 7 + min(8, 3) = 7 + 3 = 10

dp: [7, 6, 10]

更新到第三行

同理，更新 dp 数组为第三行的每个元素加上其下面行中相邻元素的较小者：

更新过程：
dp[0]: 3 + min(7, 6) = 3 + 6 = 9
dp[1]: 4 + min(6, 10) = 4 + 6 = 10

dp: [9, 10]

更新到第四行（顶行）

最后更新顶行：

更新过程：
dp[0]: 2 + min(9, 10) = 2 + 9 = 11

dp: [11]

结果

自底向上的动态规划计算结束后，dp 数组的第一个元素 11 就是从顶部到底部的最小路径和。

总结步骤

初始化 dp 数组为三角形的最后一行。
从三角形的倒数第二行开始，向上逐行更新 dp 数组，每个元素都更新为自己加上下一行相邻两个元素中较小的一个。
这个过程一直重复到三角形的顶部。
dp[0] 存储了最终的最小路径和。

方法二：递归 + 记忆化

解题步骤：

创建一个与三角形同样大小的 memo 数组，用于存储到每个元素的最小路径和，避免重复计算。
使用递归函数，从顶部开始计算每个元素到底部可能的最小路径和，将结果存储在 memo 中。
返回顶部元素的最小路径和。

Python 代码示例

def minimumTotal(triangle):
    memo = [[None] * len(row) for row in triangle]

    def helper(row, col):
        if row == len(triangle):
            return 0
        if memo[row][col] is None:
            memo[row][col] = triangle[row][col] + min(helper(row + 1, col), helper(row + 1, col + 1))
        return memo[row][col]

    return helper(0, 0)

方法三：动态规划（自顶向下）

解题步骤：

使用一个 dp 数组，初始化为三角形的第一行。
逐行更新 dp 数组，使每个元素代表从顶部到当前元素的最小路径和。
在遍历的过程中，注意边界元素的处理，因为它们只有一种选择。
最后一行中的最小值即为所求的最小路径和。

Python 代码示例

def minimumTotal(triangle):
    dp = triangle[0]
    for i in range(1, len(triangle)):
        prev = dp[:]
        for j in range(len(triangle[i])):
            if j == 0:
                dp[j] = prev[j] + triangle[i][j]
            elif j == len(triangle[i]) - 1:
                dp[j] = prev[j - 1] + triangle[i][j]
            else:
                dp[j] = min(prev[j - 1], prev[j]) + triangle[i][j]
    return min(dp)

算法分析

时间复杂度：
- 方法一和三：(O(n^2))，其中 (n) 是三角形的行数。
- 方法二：理论上也是 (O(n^2))，但由于递归调用栈的开销，可能会慢一些。
空间复杂度：
- 方法一和三：(O(n))，仅使用了一维数组进行存储。
- 方法二：(O(n^2))，使用了一个全尺寸的备忘录数组加上递归栈。