LeetCode 120. 三角形最小路径和

题目描述

难度：Middle

相关话题：数组、动态规划

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11 （即，2 +3 +5 +1 = 11）。

说明：

如果你可以只使用 O (n )的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

---

思路：

• 修改原数组：

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  for(let i=1;i<triangle.length;i++){
    for(let j=0;j<triangle[i].length;j++){
      let left=Infinity,right=Infinity
      if(j>0)left=triangle[i-1][j-1]
      if(j<triangle[i-1].length)right=triangle[i-1][j]
      triangle[i][j]+=Math.min(left,right)
    }
  }
  return Math.min.apply(Math,triangle[triangle.length-1])
};

• 不修改原数组，空间O(n)

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  let lastLayer=[triangle[0][0]]
  for(let i=1;i<triangle.length;i++){
    for(let j=lastLayer.length;j>=0;j--){
      let left=Infinity,right=Infinity
      if(j>0)left=lastLayer[j-1]
      if(j<lastLayer.length)right=lastLayer[j]
      if(lastLayer[j]==null)lastLayer[j]=0
      lastLayer[j]=triangle[i][j]+Math.min(left,right)
    }
  }
  return Math.min.apply(Math,lastLayer)
};