题解 | #最小花费爬楼梯#dp + 状态压缩

#include <iostream>
#include<vector>
#include<sstream>
using namespace std;

int main() {
    int input;
    cin >> input;
    vector<int> stairs;
    string stmp;
    getline(cin.ignore(), stmp);
    stringstream ss(stmp);
    int num;
    while (ss >> num) {
        stairs.push_back(num);
    }
    if (stairs.size() == 1) {
        cout << stairs[0];
    } else if (stairs.size() != 0) {
	   //初始状态为d(0)和d(1)
        int node1_to_now = stairs[0];//d(i-2)到d(i)所需要的最小花费
        int node2_tonow = stairs[1];//d(i-1)到d(i)所需要的最小花费
        int to_now_cost_min;//当前d(i)最小花费返回值
        int before_tonode1 = 0;//从头到d(i-2)的最小花费
        int before_tonode2 = 0;//从头到d(i-1)的最小花费
        int cost;
        for (int i = 2; i < stairs.size(); ++i) {

		  //转移方程：到达d(i)的最小花费为:从头到达d(i-1)的最小花费d(i-1)到达当前节点d(i)的最小化花费 与 从头到达d(i-2)的最小花费d(i-2)到达当前节点d(i)的最小化花费 的最小值:
            to_now_cost_min = min(node1_to_now + before_tonode1,
                                  node2_tonow + before_tonode2);

            //空间压缩，我们只需要当前节点的前两个节点的信息就够了
            node1_to_now = node2_tonow;
            before_tonode1 = before_tonode2;
            node2_tonow = stairs[i];
            before_tonode2 = to_now_cost_min;

        }
        to_now_cost_min = min(node1_to_now + before_tonode1,
                              node2_tonow + before_tonode2);
        cout << to_now_cost_min;
    }

}

// 64 位输出请用 printf("%lld")