原文：120. 三角形最小路径和(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0120/

题目：

难度：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)
};

扩展阅读：