LeetCode 题解：120. 三角形最小路径和，动态规划（从上到下），JavaScript，详细注释

/** * @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++) {      // 代入动态转移方程，若值为空则用Infinity替代，避免取最小值出错      triangle[i][j] += Math.min(        typeof triangle[i - 1][j] === 'number' ? triangle[i - 1][j] : Infinity,        typeof triangle[i - 1][j - 1] === 'number'          ? triangle[i - 1][j - 1]          : Infinity,      );    }  }
  // 所有路径和都在最后一行，需要取最小值  return Math.min(...triangle[triangle.length - 1]);};

/** * @param {number[][]} triangle * @return {number} */var minimumTotal = function(triangle) {  // 创建dp数组，长度为最后一行的长度加1。  // 默认都填入Infinity，避免递推时判断值是否存在。  // 从dp的第二个值开始递推，避免查找到-1索引的情况  let dp = new Array(triangle[triangle.length - 1].length + 1).fill(Infinity);  dp[1] = triangle[0][0] || 0; // 将第一行存入为初始值
  // 第一行自身就是路径和，因此从第二行开始递推  for (let i = 1; i < triangle.length; i++) {    // 递推当前行的路径和    for (let j = triangle[i].length - 1; j >= 0; j--) {      const index = j + 1; // 缓存上方的索引      // 代入动态转移方程      dp[index] = triangle[i][j] + Math.min(dp[index], dp[j]);    }  }
  // 所有路径和都在最后一行，需要取最小值  return Math.min(...dp);};