题目描述:
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如,给定三角形:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11
(即,2 + 3 + 5 + 1 = 11)。
思路:
自下而上,可以更好的推进最小路径,否则需要多次判断。
- 深复制一个与三角形最后一行的数组resArr,用于保存当前的路径权值
- 按照顺序计算两个相邻路径长度,取小的与上层路径长度相加并覆盖到resArr中。
- 遍历到倒数第二行停止,获取resArr第一个元素,返回
实现:
var minimumTotal = function(triangle) {
var resArr = [];
for(var i = 0; i < triangle.length; i++){
resArr[i]=triangle[triangle.length-1][i];
}
for(var i = triangle.length-1; i > 0; i--){
for(var j = 0; j < i; j++){
// 比较当前路径长度,取较小的与上层相加并覆盖
if (resArr[j] <= resArr[j+1]){
resArr[j] = resArr[j] + triangle[i-1][j];
}else{
resArr[j] = resArr[j+1] + triangle[i-1][j];
}
}
}
return resArr[0];
};