Start learning free

LESSON 239 OF 321 · DYNAMIC PROGRAMMING

Min Cost Climbing Stairs - C++ Solution and Time Complexity Analysis

Practice O(n) Read the full explanation

You get a vector cost for a staircase. You pay cost[i] when you stand on step i.

Return the smallest total you can pay to reach the top.

You start on step 0 or step 1, as you like. After you pay for a step, you climb 1 or 2 steps. The top is one step above the last step.

                        ______ top
                  __6__|
            __3__|
      __9__|
__4__|

Example 1:

Input: cost = [4, 9, 3, 6]
Output: 7
Explanation: This is the staircase in the picture.
Start on step 0 and pay 4.
Climb 2 to step 2 and pay 3.
Climb 2 more to reach the top.
In total, 4 + 3 = 7.

Example 2:

Input: cost = [5, 0]
Output: 0
Explanation: Start on step 1 and pay 0.
Climb 1 to reach the top.
The 5 on step 0 is never paid.

Example 3:

Input: cost = [2, 7, 1, 1, 8, 3, 2]
Output: 7
Explanation: Stand on steps 0, 2, 3 and 5.
That costs 2 + 1 + 1 + 3 = 7.
From step 5, climbing 2 reaches the top.

Constraints:

  • cost has 2 to 1,000 steps.
  • Each cost is from 0 to 999.

STEP 1 OF 3
    Ctrl + Enter to check

    C++ · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in C++, explained

    Understanding the Problem

    The core challenge of this problem is to find the minimum cost to reach the top of the staircase. The significance of this problem lies in its application to dynamic programming, where we need to make optimal decisions at each step to minimize the total cost. A common pitfall is to assume that starting from the first step is always the best option, which is not necessarily true.

    Approach

    To solve this problem, we can use dynamic programming. The idea is to keep track of the minimum cost to reach each step and use this information to calculate the minimum cost to reach the top.

    Naive Solution

    A naive solution would involve recursively calculating the cost for each step, but this approach is not optimal due to its exponential time complexity.

    Optimized Solution

    We can optimize the solution using dynamic programming. We will maintain an array dp where dp[i] represents the minimum cost to reach step i. The recurrence relation will be:

    dp[i] = cost[i] + min(dp[i-1], dp[i-2])
    

    We can further optimize the space complexity by using two variables instead of an array to keep track of the minimum costs for the last two steps.

    Algorithm

    1. Initialize two variables cost1 and cost2 to 0.

    2. Iterate through the cost array and update the variables using the recurrence relation.

    3. The final answer will be the minimum of cost1 and cost2.

    Code Implementation

    #include <vector>
    #include <algorithm>
    using namespace std;
    
    // Function to calculate the minimum cost to reach the top
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int cost1 = 0, cost2 = 0;
    
        // Iterate through the cost array
        for (int i = 0; i < n; ++i) {
            int currentCost = cost[i] + min(cost1, cost2);
            cost1 = cost2;
            cost2 = currentCost;
        }
    
        // The minimum cost to reach the top
        return min(cost1, cost2);
    }
    
    // Example usage
    int main() {
        vector<int> cost1 = {10, 15, 20};
        vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    
        // Output: 15
        cout << minCostClimbingStairs(cost1) << endl;
    
        // Output: 6
        cout << minCostClimbingStairs(cost2) << endl;
    
        return 0;
    }
    

    Complexity Analysis

    The time complexity of the optimized solution is O(n), where n is the length of the cost array. The space complexity is O(1) since we are using only two variables to store the minimum costs.

    Edge Cases

    Potential edge cases include:

    • Minimum length of the cost array (2 elements).
    • All elements in the cost array being zero.
    • All elements in the cost array being the maximum value (999).

    Each of these cases should be tested to ensure the algorithm handles them correctly.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple cases with small arrays.
    • Cases with alternating high and low costs.
    • Cases with all costs being the same.
    • Edge cases as mentioned above.

    Using a testing framework like Google Test can help automate and manage these tests effectively.

    Thinking and Problem-Solving Tips

    When approaching dynamic programming problems, it's crucial to:

    • Understand the problem constraints and requirements.
    • Identify the subproblems and how they relate to each other.
    • Think about the base cases and the recurrence relation.
    • Optimize space and time complexity where possible.

    Practicing similar problems and studying different algorithms can significantly improve problem-solving skills.

    Conclusion

    In this blog post, we discussed the "Min Cost Climbing Stairs" problem, explored different approaches to solve it, and provided a detailed C++ implementation. Understanding and solving such problems is essential for developing strong algorithmic thinking and problem-solving skills.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with C++1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free