120. 三角形最小路径和
题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
进阶：
你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
解题思路
若定义 f(i, j) 为 (i, j) 点到底边的最小路径和，则易知递归求解式为:
f(i, j) = min(f(i + 1, j), f(i + 1, j + 1)) + triangle[i][j]
由此，我们将任一点到底边的最小路径和，转化成了与该点相邻两点到底边的最小路径和中的较小值，再加上该点本身的值。
思路一： 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14/** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function(triangle) { const dfs = function (i, j) { if (i == triangle.length) { return 0; } return Math.min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j]; } return dfs(0, 0); };
暴力搜索会有大量的重复计算，导致 超出时间限制.
优化版本
利用二维数组进行记忆化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function(triangle) { let len = triangle.length, memo = Array.from(Array(len), () => Array(len)) const dfs = function (i, j) { if (i == len) { return 0; } if (memo[i][j] != null) { return memo[i][j]; } return memo[i][j] = Math.min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j]; } return dfs(0, 0); };
- 时间复杂度：O( n 2 n^2 n2) ，n 为三角形的行数。
- 空间复杂度：O( n 2 n^2 n2) ;
思路二： 动态规划
定义二维 dp 数组，将解法一中「自顶向下的递归」改为「自底向上的递推」。
1. 状态定义：
dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
2、状态转移：
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
3. 初始状态
一开始都初始化为0
4. 返回值
返回 dp[0][0]
实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function(triangle) { let len = triangle.length, // dp[i][j] 表示从点 (i, j) 到底边的最小路径和 dp = Array.from(Array(len + 1), () => Array(len + 1).fill(0)); // 从三角形的最后一行开始递推 for (let i = len - 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 2 n^2 n2) ，n 为三角形的行数。
- 空间复杂度：O( n 2 n^2 n2) ;
空间复杂度优化
在实际递推中我们发现，计算 dp[i][j] 时，只用到了下一行的 dp[i + 1][j] 和 dp[i + 1][j + 1] ， 因此 dp数组 定义成一维数组就行， 这样可以将将 O(
n
2
n^2
n2) 的空间复杂度优化成 O(n)
优化后代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function(triangle) { let len = triangle.length; if (len == 1) { return triangle[0][0] } let dp = Array(len + 1).fill(0); // 从三角形的最后一行开始递推 for (let i = len - 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]; };
参考资料
https://leetcode.cn/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/
最后
以上就是喜悦发夹最近收集整理的关于LeetCode 120. 三角形最小路径和120. 三角形最小路径和参考资料的全部内容，更多相关LeetCode内容请搜索靠谱客的其他文章。
发表评论 取消回复