LeetCode 120. Triangle 解题报告

题目描述

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

---

示例

Example :

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

---

注意事项

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

---

解题思路

我的思路：

这道题就是一道典型的动态规划的模板题。用minPath[i][j]表示以第i层第j个节点为终点的最小路径，因为第i层第j个节点只能从第i-1层的第j个和第j-1节点达到，那么状态转移方程为

minPath[i][j]=min(minPath[i−1][j−1],minPath[i−1][j])+triangle[i][j]

因为题目要求是O（n）的空间复杂度，而从状态转移方程可以看出求第i层的路径时只用到了第i-1层，i-2层以前的数据都不再需要，因此，可以只申请一个大小为n的vector，保存某一层的结果，由于计算时需要用到j以及j-1，因此需要从最后一个元素开始更新vector的值，状态转移方程就变成了

minPath[j]=min(minPath[j−1],minPath[j])+triangle[i][j]

由于vector初始化为0，所以对于右边界的情况可以不用考虑，而对于左边界的情况，

minPath[0]=minPath[0]+triangle[i][0]

最后找到了到第N层各元素的最小路径，通过一次遍历得到最小的路径值。整个过程可以对照着下面的实现结合画图理解。

参考思路：

惯例通过之后看了一下其他人的答案，其他人的解法是从底向上，上一层元素最小路径是由该元素的两个孩子元素求得，状态转移方程为

minpath[i]=min(minpath[i],minpath[i+1])+triangle[k][i]

最后返回minPath[0]即可。

---

代码

我的代码：

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

参考代码：

class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); vector<int> minPath(triangle.back()); for (int layer = n - 2; layer >= 0; layer--) for (int i = 0; i <= layer; i++) minPath[i] = min(minPath[i], minPath[i + 1]) + triangle[layer][i]; return minPath[0]; } };

---

总结

这道题是动态规划的模板题，状态转移方程也很容易想出来，关键的是需要知道当前层的最小路径只与相邻一层的结果相关，从而进行空间压缩，实现O（n）的空间复杂度。 本周就是做动态规划，原本还完成了LeetCode 62. Unique Path, LeetCode 63.Unique Path II 和 LeetCode 64. Minimum Path Sum，但是这几道题实在太水了，所以就不另外写解题博客了，下周再继续刷题，坚持加油~