746.min-cost-climbing-stairs.md

数组的每个索引做为一个阶梯，第  i 个阶梯对应着一个非负数的体力花费值  costi。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 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]。

---

动态规划

• dp[i] 表示到达第 i 个位置的最小花费，则有dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
• 注意：最后一步可以直接到达楼顶；我们在后面加上一个 0，不需要特殊处理边界

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        cost.push_back(0);
        int n = cost.size();
        vector<int> dp(n, 0);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++){
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
        }
        return dp[n-1];
    }
};

滚动数组优化

上面解法中，我们发现，只需要维护i-2,i-1和i三个位置

滚动数组:int dp[3];

代码实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        cost.push_back(0);
        int dp[3] = {0};
        dp[0] = cost[0];
        dp[1] = cost[1];
        dp[2] = min(dp[1], dp[0]) + cost[2];
        int n = cost.size();
        for (int i = 2; i< n; i++){
            dp[2] = min(dp[1], dp[0]) + cost[i];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[2];
    }
};