Skip to main content

三角形最小路径和

Tips

题目类型: Dynamic Programming

题目​

给定一个三角形 triangle, 找出自顶向下的最小路径和.

每一步只能移动到下一行中相邻的结点上. 相邻的结点在这里指的是下标与上一层结点下标相同或者等于**上一层结点下标 + 1 **的两个结点. 也就是说, 如果正位于当前行的下标 i, 那么下一步可以移动到下一行的下标 i 或 i + 1.

提示:
  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -10⁴ <= triangle[i][j] <= 10⁴
示例
输入: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
输出: 11
解释:

   2
  3 4
 6 5 7
4 1 8 3

自顶向下的最小路径和为 11(即 2 + 3 + 5 + 1 = 11).

题解​

二维数组​

定义二维 dp 数组, 改为自底而上递推, dp[i][j] 表示点 (i, j) 到底边的最小路径和. 状态转移方程如下:

dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
  const n = triangle.length
  const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0))

  for (let i = n - 1; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
    }
  }

  return dp[0][0]
}
  • 时间复杂度: O(n²), n 为三角形的行数
  • 空间复杂度: O(n²), n 为三角形的行数

一维数组​

在递推中我们发现, 计算 dp[i][j] 时, 只用到了下一行的 dp[i + 1][j] 和 dp[i + 1][j + 1]. 因此 dp 数组不需要定义 n 行, 只要定义一行就可以了, 这样空间复杂度就降到了 O(n).

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
  const n = triangle.length
  const dp = new Array(n + 1).fill(0)

  for (let i = n - 1; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j]
    }
  }

  return dp[0]
}