746. Min Cost Climbing Stairs

Hint

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        // Create a DP array to store the minimum cost to reach each step

        // Initialize the DP array
        // We start from step 2 because the cost to reach step 0 and step 1 is 0
        for ()
        {
            // Calculate the cost of reaching the current step from one step below
            // Calculate the cost of reaching the current step from two steps below

            // Take the minimum of the two costs to find the minimum cost to reach the current step
        }
        // The last element in the DP array contains the minimum cost to reach the top
    }
};

• DP

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)$