题目描述：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
1
2
3
4
5
6
| [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
|
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
思路：
自下而上，可以更好的推进最小路径，否则需要多次判断。
- 深复制一个与三角形最后一行的数组resArr，用于保存当前的路径权值
- 按照顺序计算两个相邻路径长度，取小的与上层路径长度相加并覆盖到resArr中。
- 遍历到倒数第二行停止，获取resArr第一个元素，返回
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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];
};
|