Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

120. 三角形最小路径和

shayue111 2019-02-07 14:56:00 阅读数:205 评论数:0 点赞数:0 收藏数:0

题目描述

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形(用二维向量triangle表示):

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

算法

利用动态规划求解自上向下的三角形路径和,难点在于要求额外的空间复杂度位O(n)。那么不妨利用传入的二维向量作为一个媒介更新dp数组。

如果没有复杂度要求的话,可以开一个二维数组dp[n][n],n是三角形的行数。从上至下的更新情况下所示:

[
[2],
[5,6],
[11,10,13],
[15,11,18,13]
]

最终返回的是dp的最后一行中最小的那个数。

现在要求空间复杂度为O(n),即最多只能开一个一维数组dp[n],n是三角形的行数。可以将dp中的数加到triangle中对应的行,最后再将triangle中对应的该行重新保存回dp。一位triangle一行最多保存n个数,所以dp[n]已经够用。详细注释在代码中给出。

代码

class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int size = triangle.size();
// 边界条件,若triangle仅有一行,直接返回第一行的该数即可
if(size == 1)
return triangle[0][0];
// 开dp数组
int dp[size];
dp[0] = triangle[0][0];
// 自三角形的第二行从上到下遍历,体现在下标为i=1。因为二维向量由i=0开始,i=0代表第一行,这里不要搞混了。
for (int i = 1; i < size; i++)
{
// 从前往后遍历triangle[i]这个向量,并用已经保存的dp数组更新triangle[i]
for (int j = 0; j <= i; j++)
{
if(j == 0)
triangle[i][j] += dp[j];
else if(j == i)
triangle[i][j] += dp[j-1];
else
triangle[i][j] += min(dp[j], dp[j-1]);
}
// 重新保存回dp数组,以用来更新三角形的下一行
for (int j = 0; j < triangle[i].size(); j++)
dp[j] = triangle[i][j];
}
// 取dp中最小的那个数返回
int _min = 99999999;
for (int j = 0; j < size; j++)
if(_min > dp[j])
_min = dp[j];
return _min;
}
};
版权声明
本文为[shayue111]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/shayue/p/10354823.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领