当前位置：首页 > news >正文

【算法】动态规划矩阵：120. 三角形最小路径和

news 2025/7/3 6:25:32

120. 三角形最小路径和

分析

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

一、题目要求

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

   23 46 5 7
4 1 8 3

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

二、核心思路

把最后一行当作“初始状态”，用一个一维数组 dp 来存它们的数值：
```
dp = [4, 1, 8, 3]
```
从下往上“合并”：看倒数第二行 [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,4]：
- dp[0] = 3 + min(7,6) = 3+6 = 9
- dp[1] = 4 + min(6,10)= 4+6 = 10
  更新后
```
dp = [9, 10]
```
再上一行就是顶点 [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+1for (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 Listdef 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 数组长度。
转移方程：

$\;=\;\text{当前格子值}\;+\;\min\bigl(\,dp[j],\,dp[j+1]\bigr).$
答案：最后剩下的 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 个数字（右下）。