题解 | 最小花费爬楼梯

#include <algorithm>
class Solution {
  public:
    
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1,0);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <=n; i++) {
            dp[i]  = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);  //dp[i] 表示到达第 i 阶（楼顶是第 n 阶）的最小成本，楼顶本身没有成本，成本来自于踩过的台阶。
        }
        return dp[n];
    }
};

//空间优化版本
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int prev2 = 0;  // 到达i-2阶的最小成本
        int prev1 = 0;  // 到达i-1阶的最小成本
        
        for (int i = 2; i <= n; i++) {
            int current = min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};