class Solution {
public:
    const int m = 1e9+7;
    using vvi = vector<vector<int>>;
    int countWays(int idx, int steps, int arrLen,vvi& dp){
        if(idx < 0 || idx >= arrLen)    return 0;
        if(steps == 0)
            if(idx != 0)  return 0;
            else return 1;
        if(dp[idx][steps] != -1)
            return dp[idx][steps];
        return dp[idx][steps] = ((countWays(idx,steps-1,arrLen,dp)%m + countWays(idx+1,steps-1,arrLen,dp)%m )%m+ countWays(idx-1,steps-1,arrLen,dp)%m)%m;
    }
    int numWays(int steps, int arrLen) {
        vvi dp;
        arrLen = min(steps/2+1,arrLen);
        dp.resize(arrLen + 1,vector<int>(steps+1, -1));
        return countWays(0, steps, arrLen,dp);
    }
};

class Solution {
public:
	//assume you are standing at the ith index and you ask should I choose (i-1)th or (i-2)th to reach the ith position then choose whichever is lesser in cost.
	// ex - > [2,3,1,1,1,4,2,1,3]
	// we insert 0 at beginning and end
	// [0,2,3,1,1,1,4,2,1,3,0], n = 11
	//we start the iteration from 2nd index 
	// [0,2,_,_,_,_,_,_,_,_,_]
	// [0,2,3,_,_,_,_,_,_,_,_]
	// [0,2,3,3,_,_,_,_,_,_,_]
	// [0,2,3,3,4,_,_,_,_,_,_]
	// [0,2,3,3,4,4,_,_,_,_,_]
	// [0,2,3,3,4,4,8,_,_,_,_]
	// [0,2,3,3,4,4,8,6,_,_,_]
	// [0,2,3,3,4,4,8,6,7,_,_]
	// [0,2,3,3,4,4,8,6,7,9,_]
	// [0,2,3,3,4,4,8,6,7,9,7]
	// our answer is 7;

    int minCostClimbingStairs(vector<int>& cost) {
        cost.insert(cost.begin() + 0, 0);
        cost.push_back(0);
        vector<int> dp(cost);
        for(int i = 2; i < dp.size() ; i++)
            dp[i] = dp[i] + min(dp[i-1],dp[i-2]);
        return dp.back();
    }
};