120. Triangle

🟠   🔖  数组 动态规划  🔗 LeetCode

题目

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output: 11

Explanation: The triangle looks like:

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

The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]

Output: -10

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

题目大意

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

解题思路

• 求出从三角形顶端到底端的最小和。要求最好用 O(n) 的时间复杂度。
• 从下往上找出最小路径和，存入数组。
• dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + input[i][j]
• 这一题普通解法是用二维数组 DP，稍微优化的解法是一维数组 DP。解法如下：

代码

// 解法一 倒序 DP，时间复杂度O(n^2)，空间复杂度 O(n^2)
const minSum = (inputArr) => {
  // 初始化dp数组
  const h = inputArr.length;
  let dp = new Array(h);
  for (let i = 0; i < h; i++) {
    dp[i] = new Array(inputArr[i].length);
  }
  // 自底向上
  for (let i = h - 1; i >= 0; i--) {
    for (let j = 0; j < inputArr[i].length; j++) {
      if (i === h - 1) {
        // 最底层就是它自己
        dp[i][j] = inputArr[i][j];
      } else {
        // 其余点的dp值 = 对应输入数组的值 + 下一层相邻两个点的dp值中最小的
        dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + inputArr[i][j];
      }
    }
  }
  return dp[0][0];
};

// 解法二 倒序 DP，压缩状态，时间复杂度O(n^2)，空间复杂度 O(n)
const minSum2 = (inputArr) => {
  const h = inputArr.length;
  // 初始化dp数组为输入最底层的值
  let dp = inputArr[h - 1];
  // 从第二层开始循环
  for (let i = h - 2; i >= 0; i--) {
    for (let j = 0; j < inputArr[i].length; j++) {
      dp[j] = Math.min(dp[j], dp[j + 1]) + inputArr[i][j];
    }
  }
  return dp[0];
};