BM64. [最小花费爬楼梯]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM64. 最小花费爬楼梯

https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7?tpId=295&sfm=discuss&channel=nowcoder

题目主要信息:

• 给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从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()];
    }
};

复杂度分析：

• 时间复杂度：，遍历一次数组
• 空间复杂度：，辅助数组dp的空间