三角形最小路径和-120

[sl1673495]

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

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

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

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

说明：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

太久没做动态规划的题了，想了好久怎么去做 DP 的表，后来发现这题的 DP 解是相对比较暴力的，状态转移方程是：

dp[level][index] = min(
   indexVal + dp[level + 1][index],
   indexVal + dp[level + 1][index + 1],
)

也就是上一层的某个 index 的最小值是由下一层的两个相邻节点的最小值所决定的。

那么先从最后一行开始求每一个下标所对应的最小路径，也就是最后一行每个下标本身的值，作为基础状态，然后向上面的行求解即可。

/**
 * @param {number[][]} triangle
 * @return {number}
 */
let minimumTotal = function (triangle) {
  let dp = []
  let n = triangle.length
  if (!n) {
    return 0
  }

  dp[n - 1] = triangle[n - 1]

  for (let i = n - 2; i >= 0; i--) {
    dp[i] = []
    let row = triangle[i]
    for (let j = 0; j < row.length; j++) {
      let curVal = row[j]
      dp[i][j] = Math.min(
        // 选择下一层同下标
        curVal + dp[i + 1][j],
        // 选择下一层next下标
        curVal + dp[i + 1][j + 1]
      )
    }
  }

  return dp[0][0]
}

当然，由于每一行的求解只依赖于下一行的最优解，所以 dp 数组可以压缩到只保存下一行的最优解：

/**
 * @param {number[][]} triangle
 * @return {number}
 */
let minimumTotal = function (triangle) {
    let n = triangle.length
    if (!n) {
        return 0
    }

    let prev = triangle[n - 1]

    for (let i = n - 2; i >= 0; i--) {
        let cur = []
        let row = triangle[i]
        for (let j = 0; j < row.length; j++) {
            let curVal = row[j]
            cur[j] = Math.min(
                // 选择下一层同下标
                curVal + prev[j],
                // 选择下一层next下标
                curVal + prev[j + 1]
            )
        }
        prev = cur
    }

    return prev[0]
}