leetcode
leetcode 651 ~ 700
使用最小花费爬楼梯

使用最小花费爬楼梯

难度:

标签:

题目描述

代码结果

运行时间: 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时,只设置了c[-1]和c[-2]的值,因为这两个值直接对应于楼梯的最后两个台阶的花费。这两个值是动态规划的基础,从这两个点开始向前计算其他所有台阶的花费。未初始化其他位置的值是因为在算法执行过程中,每个位置的值将基于之后的逻辑被计算出来。这种初始化方式确保了内存使用的效率,并且保证在计算每个台阶的最小花费时,所需的前两个值总是已经被计算过,从而避免了不必要的初始值设置。
🦆
算法中逆向计算时从倒数第三层开始,这种逆向思路是基于什么考虑?能否从底部开始正向计算达到同样的效果?
逆向计算的思路基于的考虑是,最后两层的花费已知,可以从这些已知值出发,向前计算出到达每一层楼梯的最小花费。这种逆向方法可以让我们在计算时始终保持对所需数据的即时访问。从底部开始正向计算也是可行的,即从第一层和第二层开始,逐步计算到顶部的花费,但逆向计算可以直接利用数组的最后两个元素开始,避免了额外的边界条件判断,代码实现上更为直接和清晰。
🦆
题解中提到的动态规划方法中使用了边界条件c[-1]和c[-2],这些边界条件是如何选定的,它们对解题有怎样的关键作用?
边界条件c[-1]和c[-2]是直接对应于数组中的最后两个元素,即楼梯的最后两个台阶的花费。这两个边界条件是动态规划解决方案的起点,因为达到楼梯顶部的最小花费可以从这两个台阶开始逆向计算。它们的设定是为了确保在逆向计算过程中,每一步都能基于确定的最小花费进行下一步的计算。这种设置简化了问题的复杂性,并提供了一种清晰的方法来逐步解决问题。
🦆
题解最后返回的是c[0]和c[1]的最小值,这样做的理由是什么?是否能保证这种方法总是返回全局最低花费?
该题解最后返回的是c[0]和c[1]的最小值,因为根据题目的设定,可以从第0层或第1层开始爬楼梯,且不需要支付其它额外的花费。因此,找到从这两个起点开始完成所有楼梯并达到楼顶的最小花费,就能确定整体的最小花费。由于动态规划确保了每一步都是基于最优解的决策,这种方法可以保证返回全局最低花费。

相关问题

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

 

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

 

提示:

  • 1 <= n <= 45