首页 > 代码库 > 三角形
三角形
题目:给你一个三角形,求最小路径和 例如:{{2} 所以返回2+3+5+1=11
{3 , 4}
{6, 5 , 7}
{4 , 1,8, 3}}
思路:三角形有点像树,所以可以暴力从上到下求每条路径的和在找出最小的,,但是观察可以发现,每个数只和它上面对应的数相关,也就是说它能否都被选中,依赖于它上面那层对应的“父节点”,可以采用自上而下或者自下而上,这里采用自下而上,注意;从倒数第二层开始向上走,每次统计,从下至上到达当前层每个节点的最小值,而且不需要额外空间,直接改变原数据即可,最后第一层的唯一一个节点即为所求
public int minimumTotal(List<List<Integer>> triangle) { for(int i = triangle.size() - 2; i >= 0; i--) for(int j = 0; j <= i; j++)
//当前值更新为当前值加上“左右子树”较小的值 triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1))); return triangle.get(0).get(0); }
三角形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。