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对应的值中取最小的，边界的话额外注意一下，只能是固定值。

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

最后得到末尾行树 的路径值之和对应的数组，取到里面的最小值就行了。