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();
}
};