BM64. [最小花费爬楼梯]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM64. 最小花费爬楼梯
题目主要信息:
- 给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从0开始
- 一旦支付费用，可以任意选择爬一级或是二级
- 需要求爬到顶楼，即越过数组末尾元素所需要的最小花费
- 可以从下标为0或是1的台阶开始
具体思路:
可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。
- 初始状态： 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0.
- 状态转移： 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：
。
具体过程可以参考如下图示：
代码实现:
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1, 0); //dp[i]表示爬到第i阶楼梯需要的最小花费
for(int i = 2; i <= cost.size(); i++)
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); //每次选取最小的方案
return dp[cost.size()];
}
};
复杂度分析：
- 时间复杂度：
，遍历一次数组
- 空间复杂度：
查看15道真题和解析