746. Min Cost Climbing Stairs

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        vector<int> dp(cost.size() + 1);
        for (int i = 2; i < cost.size() + 1; ++i)
        {
            int one = dp[i - 1] + cost[i - 1];
            int two = dp[i - 2] + cost[i - 2];
            dp[i] = min(one, two);
        }
        return dp.back();
    }
};

• T: $O(N)$
• S: $O(N)$

DP Improved

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        int one = 0, two = 0;
        for (int i = 2; i <= cost.size(); i++)
        {
            int temp = one;
            one = min(one + cost[i - 1], two + cost[i - 2]);
            two = temp;
        }
        return one;
    }
};

• T: $O(N)$
• S: $O(1)$