120. 三角形最小路径和

🟠   🔖  数组 动态规划  🔗 力扣 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

• 从下往上找出最小路径和，存入二维数组 DP。
• dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + input[i][j]

复杂度分析

• 时间复杂度: O(n^2)，遍历整个二维数组，其中 n 是三角形的高度。
• 空间复杂度: O(n^2)，使用了一个大小为 n^2 的二维数组来存储中间状态。

---

思路二：倒序 DP+压缩状态

• 压缩状态
• 从下往上找出最小路径和，存入一维数组 DP。
• dp[j] = Math.min(dp[j], dp[j + 1]) + inputArr[i][j]

复杂度分析

• 时间复杂度: O(n^2)，遍历整个二维数组，其中 n 是三角形的高度。
• 空间复杂度: O(n)，使用了一个长度为 n 的一维数组来存储中间状态。

代码

倒序 DP

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 + 压缩状态

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];
};