mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
49 lines
2.4 KiB
Markdown
49 lines
2.4 KiB
Markdown
# [120. Triangle](https://leetcode.com/problems/triangle/)
|
||
|
||
# 思路
|
||
给了我们一个二维数组组成的三角形，让我们寻找一条自上而下的路径，使得路径和最短，要求从上一行到下一行只能走相邻的位置。要求空间复杂度O(n)。
|
||
|
||
```
|
||
[
|
||
[1],
|
||
[2,3],
|
||
[4,5,6],
|
||
[7,8,9,10]
|
||
]
|
||
```
|
||
|
||
肯定是个动归，首先想到的是用一个二维的dp数组，但是题目要求空间复杂度O(n)，所以用一维行不行呢？
|
||
> 这种题不熟练的时候可以先用一个二维的dp数组通过后，在再此基础上改成一维dp数组。
|
||
|
||
我们开辟一个大小为n的一维数组dp，然后从最顶层往最底层循环，若当前走完了第`i`层，`dp[j]`就代表以`triangle[i][j]`为终点的最短路径和。循环完所有层后，dp数组中的最小值即所求。
|
||
|
||
那我们如何更新dp呢？若现在刚进入第`i`层，则此时dp存放有第`i-1`层的结果，即以`triangle[i-1][0, ..., i-1]`为终点的最短路径，更新dp即求以`triangle[i][0, ..., i]`为终点的最短路径。首先来看第一个点`triangle[i][0]`，它只能从上一层的第一个点到达，例如上例的2->4，所以更新即`dp[0] += triangle[i][0]`；后面的话就有两个可能了：从上一层的靠左边和靠右边到达，例如上例的2->5和3->5，我们需要从中选取最短的路径。但是需要注意的是以2为终点的最短路径和已经被上一次修改dp所覆盖了，所以我们需要在每一次修改dp前用pre做备份。则更新表达式为`dp[j] = triangle[i][j] + min(pre, dp[j])`，`pre`表示上一层的`dp[j-1]`。这样一直更新知道这一层的最后一个点，与第一个点类似，只能从上一层最后一个点到达这个点。
|
||
|
||
时间复杂度O(n^2)， 空间复杂度O(n)
|
||
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int minimumTotal(vector<vector<int>>& triangle) {
|
||
int n = triangle.size();
|
||
vector<int>dp(n, 0);
|
||
dp[0] = triangle[0][0];
|
||
int pre, tmp;
|
||
for(int i = 1; i < n; i++){
|
||
pre = dp[0];
|
||
dp[0] += triangle[i][0]; // 第一个点
|
||
for(int j = 1; j < i; j++){
|
||
tmp = dp[j];
|
||
dp[j] = triangle[i][j] + min(pre, dp[j]);
|
||
pre = tmp;
|
||
}
|
||
dp[i] = pre + triangle[i][i]; // 最后一个点
|
||
}
|
||
int res = dp[0];
|
||
for(int i = 1; i < n; i++) res = min(res, dp[i]);
|
||
return res;
|
||
}
|
||
};
|
||
``` |