首页 > 其他 > 详细

LeetCode: Triangle 题解

时间:2014-05-08 21:06:09      阅读:478      评论:0      收藏:0      [点我收藏+]

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

 

题解:

寻找三角形中,自上而下的路径中,权值和的最小值。

 

从上面的例子中,不难看出其路径的遍历方式与二叉树类似,区别就在于二叉树中 相邻两个节点的子节点都是独立的,而在三角形中,

节点 A[0] 的子节点为 B[0], B[1] ; 节点A[1]的子节点为 B[1], B[2]。 B[1]被A[0]和A[1]共享。

既然这个题目与二叉树如此类似,那么肯定能用DFS来做了,可是使用DFS必然效率不是很快,那么这道题有没有什么技巧呢?

 

可以看到题目仅仅只是需要将和给出,而并没有要求三角形中的数据不能变,那么我们可以用贪心的方法,自底向上累加,找到最小的值。

以上例中的第3行和第4行为例:
A: [6,5,7], B: [4,1,8,3]
为了描述方便,不妨设第3行为A, 第4行为B。

由于第3行的每个节点都有左右两个孩子节点, 当进行加和遍历的时候, 如果遍历到A[i] ,那么可以选择的子节点只有 B[i] 和B[i+1]。 那么在节点A[i]处的最小和就应该是 A[i] + min{B[i],B[i+1]}.

对A中各个元素求最小和,

A:   [6,5,7],
{4,1}{1,8},{8,3}
A‘: [6+1, 5+1, 7+3] B: [4,1,8,3]

可得到 A‘= {7,6,10}

向上递归,可知 triangle的首元素 triangle[0][0],必定为最小和。

 

bubuko.com,布布扣
 1 class Solution {
 2 public:
 3     int minimumTotal(vector<vector<int> > & triangle)
 4     {
 5         vector<int> vi;
 6         int len = triangle.size();
 7         if(1==len) return triangle[0][0];
 8     
 9         int i,j;
10         for(i=len-2;i>=0;--i)
11         {
12             for(j=0;j<triangle[i].size();j++)
13             {
14                 triangle[i][j]+= (triangle[i+1][j]<triangle[i+1][j+1]?triangle[i+1][j]:triangle[i+1][j+1]);  // 贪心策略
15             }
16         }
17         return triangle[0][0];
18     }
19 };
bubuko.com,布布扣

 转载请注明出处: http://www.cnblogs.com/double-win/ 谢谢

LeetCode: Triangle 题解,布布扣,bubuko.com

LeetCode: Triangle 题解

原文:http://www.cnblogs.com/double-win/p/3709291.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!