46 | 面试题：三角形的最小路径和-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 46 | 面试题：三角形的最小路径和

在算法面试中，动态规划（Dynamic Programming, DP）是一类极其重要且频繁出现的题目类型，它要求我们将原问题分解为相对简单的子问题，并存储子问题的解以避免重复计算，从而高效地解决复杂问题。其中，“三角形的最小路径和”便是一个典型的动态规划问题，它不仅考察了面试者对DP原理的理解，还检验了其在具体场景下的应用能力。

#### 问题描述

给定一个三角形 `triangle`，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如，给定三角形如下：

```
   2
  3 4
 6 5 7
4 1 8 3
```

自顶向下的最小路径和为 `11`（即，2 + 3 + 5 + 1 = 11）。

#### 解题思路

要解决这个问题，我们可以采用自底向上的动态规划方法。从三角形的底部开始，逐步向上计算到达每个位置的最小路径和。具体地，对于三角形中的每个位置 `(i, j)`（其中 `i` 表示行号，从0开始；`j` 表示列号，同样从0开始），其最小路径和等于它本身的值加上其正下方相邻位置 `(i+1, j)` 和 `(i+1, j+1)` 中的较小值的最小路径和（注意边界条件）。

#### 算法步骤

1. **初始化**：创建一个与原始三角形相同大小的二维数组 `dp`，用于存储到达每个位置的最小路径和。由于我们是从底部开始计算，所以可以直接将 `triangle` 的最后一行复制到 `dp` 的最后一行，因为到达这些位置的最小路径和就是它们自身的值。

2. **动态规划**：从倒数第二行开始，向上遍历三角形的每一行。对于每一行中的每个位置 `(i, j)`，计算其最小路径和：`dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])`。这里需要注意边界条件，特别是当 `j` 为0或 `j` 等于当前行的最后一个元素索引时，只需考虑一侧的相邻元素。

3. **结果**：最终，`dp[0][0]` 将存储从三角形顶部到底部的最小路径和。

#### 代码实现

以下是上述思路的Python代码实现：

```python
def minimumTotal(triangle):
    if not triangle:
        return 0
    
    # 获取三角形的行数
    rows = len(triangle)
    
    # 创建一个与triangle相同大小的dp数组
    dp = [[0] * len(row) for row in triangle]
    
    # 初始化dp数组的最后一行
    for j in range(rows):
        dp[rows-1][j] = triangle[rows-1][j]
    
    # 从倒数第二行开始向上计算
    for i in range(rows-2, -1, -1):
        for j in range(len(triangle[i])):
            # 注意边界条件
            if j == 0:
                dp[i][j] = triangle[i][j] + dp[i+1][j]
            elif j == len(triangle[i]) - 1:
                dp[i][j] = triangle[i][j] + dp[i+1][j]
            else:
                dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])
    
    # 返回顶部的最小路径和
    return dp[0][0]

# 示例
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
print(minimumTotal(triangle))  # 输出: 11
```

#### 复杂度分析

- **时间复杂度**：O(n^2)，其中n是三角形的行数（也是列数的最大值，因为三角形是等腰的）。我们需要遍历三角形的每个元素一次来计算最小路径和。
- **空间复杂度**：O(n^2)。我们使用了一个与原始三角形大小相同的二维数组来存储中间结果。然而，注意到我们实际上只需要知道前一行的信息来计算当前行的最小路径和，因此可以通过使用一维数组来优化空间复杂度至O(n)。

#### 优化空间复杂度

为了进一步优化空间复杂度，我们可以只使用一个一维数组来存储每一行的最小路径和。在遍历每一行时，我们更新这个数组，使其反映当前行的最小路径和。由于我们是从底部向上遍历的，因此可以安全地覆盖旧的数据，因为后续的计算不会再用到它们。

```python
def minimumTotalOptimized(triangle):
    if not triangle:
        return 0
    
    rows = len(triangle)
    dp = triangle[-1][:]  # 使用最后一行作为dp数组的初始值
    
    # 从倒数第二行开始向上遍历
    for i in range(rows-2, -1, -1):
        for j in range(len(triangle[i])):
            # 更新dp数组中的值
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1]) if j < len(dp) - 1 else triangle[i][j] + dp[j]
    
    return dp[0]

# 使用优化后的函数
print(minimumTotalOptimized(triangle))  # 输出: 11
```

在这个优化版本中，我们直接在原始三角形的最后一行上进行操作，避免了额外的空间开销。这种方法不仅减少了空间复杂度，还保持了相同的时间复杂度O(n^2)。

#### 总结

“三角形的最小路径和”是一个经典的动态规划问题，它展示了如何通过将问题分解为子问题并存储中间结果来高效地解决问题。通过这个问题，我们可以深入理解动态规划的核心思想，并学会如何在具体场景中应用这一强大的算法工具。此外，通过优化空间复杂度的练习，我们也能够提升对算法空间效率的关注，从而编写出更加高效、紧凑的代码。

该分类下的相关小册推荐：

数据结构与算法(中)

数据结构与算法(上)

数据结构与算法之美

编程之道-算法面试(下)

业务开发实用算法精讲

编程之道-算法面试(上)

数据结构与算法(下)