class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 状态表示：f[i]表示到达第i个台阶的最小花费
        // 状态计算：f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        // 边界设置：
        int n = cost.size();
        vector<int> f(n + 1);
        f[0] = 0, f[1] = 0;
        for (int i = 2; i <= cost.size(); i ++) {
            f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }
        return f[n];
    }
};

空间上还可以优化到O(n)

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 状态表示：f[i]表示到达第i个台阶的最小花费
        // 状态计算：f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        // 边界设置：
        int n = cost.size();
        int a = 0, b = 0, c;
        for (int i = 2; i <= cost.size(); i ++) {
            c = min(b + cost[i - 1], a + cost[i - 2]);
            a = b;
            b = c;
        }
        return c;
    }
};

进阶：输出路径

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 状态表示：f[i]表示到达第i个台阶的最小花费
        // 状态计算：f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        // 边界设置：
        int n = cost.size();
        vector<int> f(n + 1);
        vector<int> path(n + 1);
        path[0] = -1, path[1] = -1;
        f[0] = 0, f[1] = 0;
        for (int i = 2; i <= cost.size(); i ++) {
            if (f[i - 1] + cost[i - 1] <= f[i - 2] + cost[i - 2]) {
                path[i] = i - 1;
            } else {
                path[i] = i - 2;
            }
            f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }

        // cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
        // 输出路径：0 2 4 6 7 9 
        int t = path[n]; stack<int> stk; 
        while (t != -1) stk.push(t), t = path[t];

        while(stk.size()) {
            cout << stk.top() << " ";
            stk.pop();
        }
        cout << endl;

        return f[n];
    }
};