首先明白我们要解决的问题是什么：

如何用最小花费，越过这个数组的末尾

我们现在设这个数组的下标为[0, i], 想要达到越过末尾这个目标（到达i+1的位置），有两种可能：

  • 从 i 级往上走一步
  • 从 i-1 级往上走两步

现在，我们设 dp[i] 为，走到 i 级的最小花费（表示最后一级是i级，全程最小花费是多少）

那么，想要越过末尾，到达i+1的位置，我们就要 min(dp[i], dp[i-1])

以此类推：看起来目前我们需要求出 dp[i]和dp[i-1] 的值

dp[i] = min(dp[i-1], dp[i-2])
dp[i-1] = min(dp[i-2], dp[i-3])

不管是到了哪一级，想知道最小花费，都要知道两个因素：

  • 自己的前一级多少花费
  • 前两级多少花费

取小值，然后加上当前台阶的值，就是到了当前台阶要花费的最小值，于是，我们得到了演变方程

dp[i] = min(dp[i-1], dp[i-2])+cost[i]

c++实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()); //dp[i] 表示最后一级是i级，最小花费是多少
        dp[0] = cost[0];  //最后一级是0级，再迈一步或者两步即可上顶，那只需要支付0级的费用
        dp[1] = cost[1];  //最后一级是1级，再迈一步或者两步即可上顶，因为可以选择直接从1级开始，所以只需要支付1级的费用
        for(int i=2; i<cost.size(); i++){
            dp[i] = min(dp[i-1], dp[i-2])+cost[i];  //到i级最小花费，就是dp[i-1]和dp[i-2]最小值加上当前i级的花费
        }
        return min(dp[cost.size()-1], dp[cost.size()-2]); //要到顶，那就要下标为-1或-2的最小值
    }
};

优化版

因为我们可以看到dp[0]、dp[1]正好和cost[0]、cost[1]相等，我们可以利用一下cost

这样空间复杂度就从O(n)变成了O(1)

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