首页 > 代码库 > Leetcode Triangle
Leetcode Triangle
/* 意思就是: 给定一个三角形,求得和最小的路径。每层只能选一个整数,上一层和下一层的整数必须是相邻的。 思路: 1,动态规划。到第i层的第k个顶点的最小路径长度表示为f(i,k),则f(i, k) = min{f(i-1,k), f(i-1,k-1)} + d(i, k); 其中d(i, k)表示原来三角形数组里 的第i行第k列的元素。则可以求得从第一行到最终到第length-1行第k个元素的最小路径长度,最后再比较第length-1行中所有元素的路径长度大小,求得最小值。 2,本题主要关心的是空间复杂度不要超过n。 3,注意边界条件——每一行中的第一和最后一个元素在上一行中只有一个邻居。而其他中间的元素在上一行中都有两个相邻元素。 示例: 初始 triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] 程序运行之后的triangle [ [2], [5,6], [11,10,13], [15,11,18,16] ] */ class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int size = triangle.size(); if(size == 0){ return 0; } int i = 0; int j = 0; int innerSize = 0; int minPath = 0x7FFFFFFF; for(i = 1; i < size; i++){ innerSize = triangle[i].size(); for(j = 0; j < innerSize; j++){ if(j == 0){ triangle[i][0] += triangle[i-1][0]; } else if(j == innerSize - 1){ triangle[i][innerSize - 1] += triangle[i -1][innerSize - 2]; } else { triangle[i][j] += min(triangle[i - 1][j-1], triangle[i - 1][j]); } } } innerSize = triangle[size - 1].size(); for(j = 0; j < innerSize; j++){ if(triangle[size -1][j] < minPath){ minPath = triangle[size -1][j]; } } return minPath; } };
Leetcode Triangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。