1. 题目描述
给定一个三角形 triangle
,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i
,那么下一步可以移动到下一行的下标 i
或 i + 1
。
示例 1:
输入: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)。
示例 2:
输入:triangle = [[-10]]
输出:-10
提示:
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10 <= triangle[i][j] <= 10
进阶:你可以只使用
O(n)
的额外空间(n
为三角形的总行数)来解决这个问题吗?2. 解题思路
这道题目和最小路径和那道题的阶梯思路类似,都是使用动态规划来解决。
这里,其实我们并不需要初始化一个数组来保存每一步的状态(每个节点的最小路径值),可以在原数组上进行操作,因为每个节点都只遍历一次,在遍历完之后,我们只需要将当前节点的状态赋值给当前节点即可。
这里同样需要处理两个边界的问题,对于第一列元素,他只能是上面的元素下来的,所以他的状态转移方程是:
triangle[i][j] += triangle[i - 1][j]
对于每一行的最后一位,它只能是上一行的最后一位下来的,所以他的状态转移方程是:
triangle[i][j] += triangle[i - 1][j - 1]
对于其他的元素,可以是其对应序号以及对应序号减一的元素移动下来的,所以他的状态转移方程是:
triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])
最后我们只需要返回最后一行元素的最小值即可,这里我们用…扩展运算符配合Math的min方法求得最后一行的最小值。
复杂度分析:
- 时间复杂度:O(n),其中 n 是三角形的行数。
空间复杂度:O(1)。这里我们在原数组的基础上进行的操作,所以所需要的额外的空间为常数。
3. 代码实现
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
const n = triangle.length
for(let i = 1; i < n; i++){
for(let j = 0; j <= i; j++){
if(j === 0){
triangle[i][j] += triangle[i - 1][j]
}else if(j === i){
triangle[i][j] += triangle[i - 1][j - 1]
}else{
triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])
}
}
}
return Math.min(...triangle[n - 1])
};
4. 提交结果