使用最小花费爬楼梯
难度:
标签:
题目描述
代码结果
运行时间: 18 ms, 内存: 16.1 MB
/*
题目思路:
利用Java Stream的特点来简化代码。我们依然使用动态规划的思想,使用reduce方法来累积计算到达每个台阶的最小花费。
*/
import java.util.stream.IntStream;
public class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
return IntStream.range(2, n)
.mapToObj(i -> cost[i] + Math.min(cost[i - 1], cost[i - 2]))
.reduce((acc, minCost) -> acc + minCost)
.orElse(Math.min(cost[n - 1], cost[n - 2]));
}
}
解释
方法:
这个题解使用动态规划的思路来解决问题。它从楼梯顶部开始,逆向计算到达每一层台阶的最小花费。对于每一层台阶,可以从它的前一层或前两层到达,因此取两者的最小值,再加上当前层的 cost 即可。最后返回起始的第一层和第二层的最小值。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在初始化数组c时,为什么只设置了c[-1]和c[-2]的值,并没有初始化其它位置的值?这种初始化对算法的执行有何影响?
▷🦆
算法中逆向计算时从倒数第三层开始,这种逆向思路是基于什么考虑?能否从底部开始正向计算达到同样的效果?
▷🦆
题解中提到的动态规划方法中使用了边界条件c[-1]和c[-2],这些边界条件是如何选定的,它们对解题有怎样的关键作用?
▷🦆
题解最后返回的是c[0]和c[1]的最小值,这样做的理由是什么?是否能保证这种方法总是返回全局最低花费?
▷