描述
给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
样例
比如,给出下列数字三角形:
复制代码
1
2
3
4
5
6
7[ [2], [3,4], [6,5,7], [4,1,8,3] ]
从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
思路:大家不要被这个样例所迷惑,这个题目的用意不是找每行的最小值,而是去找最短路径,所以数不能跨越两个数来比较。
就是把数组中数两两比较,去最小的值与上一层的父节点相加,这样循环,最后最短路径和即为根节点。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12public int minimumTotal(int[][] triangle) { int len = triangle.length; for (int i = len - 2; i >= 0; i--) { int len1 = triangle[i].length; for (int j = 0; j < len1; j++) { triangle[i][j] = triangle[i][j]+Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]); } } return triangle[0][0]; }
最后
以上就是害怕帅哥最近收集整理的关于数字三角形的最短路径的全部内容,更多相关数字三角形内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复