优化网站公司哪家口碑好,做啥网站好,网页微博怎么切换账号,重庆建设工程施工安全管理信息网LeetCode刷题记录 #x1f310; 我的博客主页#xff1a;iiiiiankor#x1f3af; 如果你觉得我的内容对你有帮助#xff0c;不妨点个赞#x1f44d;、留个评论✍#xff0c;或者收藏⭐#xff0c;让我们一起进步#xff01;#x1f4dd; 专栏系列#xff1a;LeetCode…
LeetCode刷题记录 我的博客主页iiiiiankor 如果你觉得我的内容对你有帮助不妨点个赞、留个评论✍或者收藏⭐让我们一起进步 专栏系列LeetCode 刷题日志 文章内容来自我的学习与实践经验如果你有任何想法或问题欢迎随时在评论区交流讨论。让我们一起探索更多的可能 题目链接120. 三角形最小路径和
题目描述
给定一个三角形triangle 找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 1 的两个结点。也就是说如果正位于当前行的下标i那么下一步可以移动到下一行的下标 i 或 i 1 。
示例 1
输入triangle [[2],[3,4],[6,5,7],[4,1,8,3]]
输出11
解释如下面简图所示23 46 5 7
4 1 8 3
自顶向下的最小路径和为 11即2 3 5 1 11。示例 2
输入triangle [[-10]]
输出-10提示
1 triangle.length 200triangle[0].length 1triangle[i].length triangle[i - 1].length 1-10^4 triangle[i][j] 10^4
如图所示 例子 [[20],[30,40],[60,50,70],[40,10,80,30]] 思路1从上开始dp
分析
class Solution {
public:int minimumTotal(vectorvectorint triangle) {if(triangle.empty()) return 0;int row triangle.size();vectorvectorint dp(row);for(size_t i 0;irow;i){dp[i].resize(triangle[i].size(),0);}//初始化dp[0][0] triangle[0][0];//状态转移for(size_t i 1;irow;i){for(size_t j 0;ji;j){if(j0) dp[i][j]dp[i-1][j] triangle[i][j];else if(ji) dp[i][j]dp[i-1][j-1]triangle[i][j];else{dp[i][j] min( dp[i-1][j-1], dp[i-1][j] ) triangle[i][j];}}}//最后一行int min_s dp[row-1][0];for(size_t i 1;i dp[row-1].size();i){min_s min(dp[row-1][i],min_s);}return min_s;}
};思路2从下向上dp优化空间复杂度
思路1的时间复杂度为O(n^2)显然空间复杂度过高了可以优化为O(n)思想如下
class Solution {
public:int minimumTotal(vectorvectorint triangle) {if(triangle.empty()) return 0;int row triangle.size();vectorint dp(triangle[row-1].size());//初始化for(size_t i 0;idp.size();i){dp[i] triangle[row-1][i];}//状态转移for(int i row-2;i0;--i){for(int j 0;jtriangle[i].size();j){dp[j] triangle[i][j] min(dp[j],dp[j1]);}}//最后一行return dp[0];}
};
