Min Cost Climbing Stairs

Problem

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Constraints

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Solution

The problem Min Cost Climbing Stairs can be solved using a dynamic programming. Let F(i) be the minimum cost to climb ith step on a staircase. Then F(i) = min(F(i - 1), F(i - 2)) + costi holds true for `i >= 2`. Therefore, we calculate the minimum cost to reach the top of the floor by calculating the minimum cost to reach each steps on the staircase.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

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

        return cost.back();
    }
};