关于javascript:Leetcode120三角形最小路径和

Leetcode120 三角形最小门路和

给定一个三角形 triangle，找出自顶向下的最小门路和。

每一步只能挪动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 雷同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于以后行的下标 i，那么下一步能够挪动到下一行的下标 i 或 i + 1。

答题：

/**
 \* @param {number[][]} triangle
 \* @return {number}
 */
var minimumTotal = function(triangle) {let pre = [0]
  while(triangle.length){​    let curr = triangle.shift()
​    let newLen = []
​    curr.forEach((length,index)=>{​      if(index === 0){​      newLen.push(pre[0]+length)
​      }else if(index === curr.length-1){​        newLen.push(pre[index-1]+length)
​      }else{​        newLen.push(Math.min(pre[index - 1],pre[index])+length)
​      }
​    })
​    pre = newLen
  }
  return Math.min(...pre)
};

原本感觉本人可能答复的没有官网的快，但实际上比照下来，这个解法也不慢啊，而且简略易懂。

对应第 n 行的门路是上一行 index- 1 对应的值和 index 对应的值中取最小的，边界的话额定留神一下，只能是固定值。

这样从上往下进行计算即可。

最初失去开端行树 的门路值之和对应的数组，取到外面的最小值就行了。