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

// 力扣 最小花费爬楼梯
// 动态规划

// 状态表示： dp[i]: i为起点到楼顶的总花费
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        vector<int> dp(n);
        dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
        for(int i = n - 3; i >= 0; i--)
        {
            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
        }
        return min(dp[0], dp[1]);
    }
};

// 状态表示： dp[i]: i为结束位置的总花费
/* class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1);
        dp[0] = 0, dp[1] = 0;
        int tmp1, tmp2;
        for(int i = 2; i <= n; i++)
        {
            tmp1 = cost[i - 1] + dp[i - 1];
            tmp2 = cost[i - 2] + dp[i - 2];
            dp[i] = tmp1 < tmp2 ? tmp1 : tmp2;
        }
        return dp[n];
    }
}; */