【面试经典150 | 动态规划】三角形最小路径和

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【动态规划】【数组】

---

题目来源

120. 三角形最小路径和

---

解题思路

方法一：动态规划

定义状态

f[i][j] 表示从三角形顶部到达位置 (i, j) 的最小路径，i 和 j 分别表示 triangle 数组中的第 i 个数组中的第 j 个元素（索引从 0 开始）。

转移关系

由于每一步只能移动到下一行的「相邻节点」，因此要到达位置 (i, j) 处，上一步只能在位置 (i-1, j) 或 (i-1, j-1)。我们需要在这两个位置中选择一个路径和较小的进行转移，转移关系为：

$$f[i][j]=min(f[i-1][j],f[i-1][j-1])+triangle[i][j]$$

base case

边界情况有三种，一是初始位置 f[0][0] = triangle[0][0].

二是对于每个数组中的第一个位置，即 f[i][j] 中 j = 0 的情况，上一个位置只能是 (i-1, j)，因此此时有：

$$f[i][0]=f[i-1][j]+triangle[i][j],i>=1$$

三是 i = j 时，上一个位置只能是 (i-1, j-1)，因此有：

$$f[i][i]=f[i-1][i-1]+triangle[i][i],i=j$$

最后返回

最后返回数组 f[n-1] 中的最小值。

实现代码

class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int n = triangle.size();vector<vector<int>> f(n, vector<int>(n));f[0][0] = triangle[0][0];for (int i = 1; i < n; ++i) {f[i][0] = f[i-1][0] + triangle[i][0];for (int j = 1; j < i; ++j) {f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j];}f[i][i] = f[i-1][i-1] + triangle[i][i];}return *min_element(f[n-1].begin(), f[n-1].end());}
};

复杂度分析

时间复杂度：$O(n^2)$，$n$ 是三角形的行数。

空间复杂度：$O(n^2)$。我们需要一个 $n\times n$ 的二维数组存放所有的状态。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。