120. 三角形最小路径和

分析

下面用**“自底向上”＋“一维滚动数组”** 的方式，用最通俗的语言来讲解，并给出 C++ 和 Python 的代码。

---

一、题目要求

给你一个「数值三角形」 triangle，形状类似这样（共 4 行）：

   2
  3 4
 6 5 7
4 1 8 3

• 起点：第一行中间的 2。
• 终点：最后一行的某个数字（可以选最小的那一条路走到终点）。
• 移动规则：每次只能往下一行走，而且只能走到「与自己位置同列」或「列索引+1」的那个数字。
• 目标：从顶点走到底部，经过的数字之和最小是多少？

---

二、核心思路

1. 把最后一行当作“初始状态”，用一个一维数组 dp 来存它们的数值：

   dp = [4, 1, 8, 3]
   

2. 从下往上“合并”：看倒数第二行 [6,5,7]，对于每个位置 j，往下能走的位置就是 dp[j] 和 dp[j+1]，取两者中较小的再加上当前格子值，就是从这里出发到底部的最小总和。

   • 新的 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]   （长度变成 3）
   

3. 继续往上：看再上一行 [3,4]：

   • dp[0] = 3 + min(7,6) = 3+6 = 9
   • dp[1] = 4 + min(6,10)= 4+6 = 10
     更新后

   dp = [9, 10]
   

4. 再上一行就是顶点 [2]：

   • dp[0] = 2 + min(9,10) = 2+9 = 11
     最终 dp = [11]，里面唯一的值 11 就是「自顶向下、可选路径最小的总和」。

为什么这样对？

• 每次「往上一行」时，都在模拟「如果我站在这一行的第 j 个数，用最优策略走到底部，能拿到的最小和」——它只依赖于它下面两个相邻位置最优值。
• 一维数组不断缩短，最后只剩顶点的最优值。

这个方法 只用 O(n) 的额外空间（n 为行数），也非常高效。

---

三、代码实现

C++ 版本

#include <bits/stdc++.h>
using namespace std;

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    // dp 初始化为最后一行
    vector<int> dp(triangle.back());
    // 从倒数第二行往上“合并”
    for (int i = n - 2; i >= 0; --i) {
        // 新 dp 大小是 i+1
        for (int j = 0; j <= i; ++j) {
            // 取下面两个相邻位置的较小值，加上当前格子
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
        }
    }
    // 最终 dp[0] 就是答案
    return dp[0];
}

int main() {
    int n;
    cin >> n;  // 读入三角形行数
    vector<vector<int>> triangle(n);
    for (int i = 0; i < n; ++i) {
        triangle[i].resize(i+1);
        for (int j = 0; j <= i; ++j) {
            cin >> triangle[i][j];
        }
    }
    cout << minimumTotal(triangle) << "\n";
    return 0;
}

Python 版本

from typing import List

def minimum_total(triangle: List[List[int]]) -> int:
    # dp 初始化为最后一行
    dp = triangle[-1].copy()
    # 从倒数第二行往上
    for i in range(len(triangle)-2, -1, -1):
        for j in range(i+1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    return dp[0]

if __name__ == "__main__":
    n = int(input().strip())  # 行数
    triangle = []
    for i in range(n):
        row = list(map(int, input().split()))
        triangle.append(row)
    print(minimum_total(triangle))

---

小结

• 状态定义：dp[j] 表示「从当前行第 j 列开始走到最底行的最小路径和」。

• 计算顺序：从底层往上层，逐行更新 dp 数组长度。

• 转移方程：

  $$dp[j]=\text{当前格子值}+\min (dp[j],dp[j+1]).$$

• 答案：最后剩下的 dp[0]。

这样既直观，又只用了 O(n) 的额外空间。

---

题目需求

想像这个三角形像一座阶梯，每一层多一个台阶，从顶上往下走，每次只能往“左下”或者“右下”跨一步：

       [2]          ← 第 0 行，只有一个台阶
      /   \
    [3]   [4]       ← 第 1 行，两个台阶
   /   \ /   \
 [6]  [5]  [7]     ← 第 2 行，三个台阶
 / \  / \  / \
[4][1][8][3]      ← 第 3 行，四个台阶

• 起点：第一行的 2。

• 终点：最后一行（包含 4,1,8,3）里的某一个数字。

• 移动规则：

  • 如果你在行 i 的第 j 个数字上（记作 triangle[i][j]），
  • 下一步可以走到行 i+1 的第 j 个数字（左下），
  • 或者走到行 i+1 的第 j+1 个数字（右下）。

用更直白的话说：

1. 站在 2 上，你可以往下走一步到 3，也可以往右下走一步到 4。
2. 比如你先选了 3，那么再走时就可以从 3 走到下面一行的 6（左下）或 5（右下）。
3. 如果你先选了 4，下一步可以从 4 走到它下面的 5（左下）或 7（右下）。
4. 一直这样选，直到走到最底层。

---

举个完整的路径例子

• 路径 1：2 → 3 → 6 → 4
• 路径 2：2 → 3 → 6 → 1
• 路径 3：2 → 3 → 5 → 1 ← 这是最小和的那条
• 路径 4：2 → 3 → 5 → 8
• 路径 5：2 → 4 → 5 → 1
• 路径 6：2 → 4 → 5 → 8
• 路径 7：2 → 4 → 7 → 8
• 路径 8：2 → 4 → 7 → 3

计算它们的数字之和：

• 路径 3 的和是 2+3+5+1=11，比其它所有路径都小，所以答案就是 11。

---

希望这样“画台阶＋列出几条具体路径”的方式，能让你直观地明白：

• 每步只能往左下或右下，
• 从顶点走到底部，选一条数字和最小的路线。