三角形最小路径和-120 #80

sl1673495 · 2020-06-16T03:11:10Z

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

相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 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]
}

sl1673495 added 动态规划待复习 labels Jun 16, 2020

sl1673495 changed the title ~~三角形最小路径和-130~~ 三角形最小路径和-120 Jun 16, 2020

Oct	NOV	Dec
	29
2019	2020	2021

sl1673495 / leetcode-javascript

三角形最小路径和-120 #80

三角形最小路径和-120 #80

sl1673495 commented Jun 16, 2020 •

edited

sl1673495 / leetcode-javascript

Join GitHub today

GitHub is where the world builds software

三角形最小路径和-120 #80

三角形最小路径和-120 #80

Comments

sl1673495 commented Jun 16, 2020 • edited

思路

Essential cookies

Always active

Analytics cookies

sl1673495 commented Jun 16, 2020 •

edited