C语言重构【746】使用最小花费爬楼梯

电玩女神 2022-12-29 09:29 113阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
    
    每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
    
    您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
    
    示例 1:
    
    输入: cost = [10, 15, 20]
    输出: 15
    解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
     示例 2:
    
    输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    输出: 6
    解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
    注意：
    
    cost 的长度将会在 [2, 1000]。
    每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

#### 方案： ####

class Solution
    { 
    public:
        int minCostClimbingStairs(vector<int> &cost)
        { 
            //动规即可
            int len = cost.size();
            //基本情况，好像不用考虑也可以通过,发现后面给了数组长度范围
            // if(len==1) return 0;
            // else if(len==2) return min(cost[0],cost[1]);
            //填数组
            for (int i = 2; i < len; i++)
                cost[i] += min(cost[i - 1], cost[i - 2]);
            //决定方案
            return min(cost[len - 2], cost[len - 1]);
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1),由于用的原数组当dp数组，故常数个辅助变量

[Git]: https://github.com/ch98road/leetcode