STUNT - Editorial

editorial
1

Question Link

Difficulty
Simple

Prerequisite
DP

Explanation

There is a clear recursion available:
The final cost = f[i] to climb the staircase from some step i is
f[i] = cost[i] + min(f[i+1], f[i+2]).
This motivates dynamic programming.

Author's Solution 
#include<bits/stdc++.h>
#define ll long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#define N 100000000
#define mod 1000000007
#define inf LLONG_MAX
    
template <typename T>
void print(T x){cout<<x<<"\n";}
template <typename T1, typename T2>
void print2(T1 x,T2 y){cout<<x<<" "<<y<<"\n";}
template <typename T1, typename T2,typename T3>
void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<"\n";}



int main()
{
    io;
    ll test_case;
    test_case=1;
    while(test_case--)
    {
        int n;
        cin>>n;

        vector<int> cost(n);
        for(int i=0;i<n;i++) cin>>cost[i];
        
        for(int i=2;i<n;i++)
        cost[i]+=min(cost[i-1],cost[i-2]);

        print(min(cost[n-1],cost[n-2]));
    }
}