# 746.使用最小花费爬楼梯

## 题目描述
[746.使用最小花费爬楼梯](https://leetcode.cn/problems/min-cost-climbing-stairs/)

## 解题思路
相当于[爬楼梯](https://zwyyy456.vercel.app/zh/posts/tech/70.%E7%88%AC%E6%A5%BC%E6%A2%AF/)的进阶版，递推关系变复杂了一些，但本质没有变。
$a_n = min(a_{n - 1} + cost[i - 1], a_{n - 2} + cost[i - 2])$
写出递推关系后就能很方便地写出`for`循环来遍历求解。

## 代码
```cpp
#include <vector>
using std::vector;
class Solution {
  public:
    int minCostClimbingStairs(vector<int> &cost) {
        int sz = cost.size();
        vector<int> dp(2);
        dp[0] = dp[1] = 0;
        // dp[2] = cost[0] < cost[1] ? cost[0] : cost[1];
        for (int i = 2; i <= sz; i++) {
            // 原始版本
            // dp[i] = (dp[i - 2] + cost[i - 2]) < (dp[i - 1] + cost[i - 1]) ? (dp[i - 2] + cost[i - 2]) : (dp[i - 1] + cost[i - 1]);
            // 空间优化版本：
            int res = dp[0] + cost[i - 2] < dp[1] + cost[i - 1] ? dp[0] + cost[i - 2] : dp[1] + cost[i - 1];
            dp[0] = dp[1];
            dp[1] = res;
        }
        return dp[1];
    }
};
```