首页 > 代码库 > leetcode第一刷_Triangle
leetcode第一刷_Triangle
非常easy的一道DP,看到空间限制是O(N)的,不要习惯性的以为是要保存每一行的最小值,不难想到是要保存一行其中各个数为路径终点时的和的大小。当算到最后一行时,就是从顶部究竟部以这个底部位置为终点的最短路径和,找一个最小的就能够了。
实现的时候要注意个问题,由于计算时要用到上一行的数据,所以为了避免数据被覆盖,应该从后往前算,这个技巧用的非常多,相信大家都非常熟悉。
ac代码例如以下:
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int lines = triangle.size(); if(lines == 0) return 0; vector<int> res(lines, 0); for(int i=0;i<lines;i++){ if(i>0) res[i] = res[i-1]+triangle[i][i]; for(int j=i-1;j>0;j--){ res[j] = min(res[j-1], res[j])+triangle[i][j]; } res[0] = res[0]+triangle[i][0]; } int mmin = res[0]; for(int i=1;i<lines;i++){ if(res[i]<mmin) mmin = res[i]; } return mmin; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。