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