题解 | 最小花费爬楼梯

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;

//const int N=;
int n;

int main()
{
    IOS
    cin>>n;
    vector<int> a(n), f(n+2, 1e9);
    for(int i=0; i<n; i++) cin>>a[i];
    f[0]=0, f[1]=0;
    for(int i=2; i<=n; i++){
        f[i]=min({f[i], f[i-1]+a[i-1], f[i-2]+a[i-2]});
    }
    cout<<f[n];
    return 0;
}

动态规划，f[i]表示到第i个台阶的最小消费值。索引均从0开始

f[0]=f[1]=0是初始条件，注意更新时最大到f[n]

#牛客春招刷题训练营#