We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Min Cost Climbing Stairs

Number: 747

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft, Adobe, Uber, Bloomberg, Accenture

Problem Description

Given an array where each element represents the cost to step on that stair, determine the minimum cost needed to reach the top of the floor. You can start at index 0 or 1 and you can move either one or two steps after paying the cost on the step.

Key Insights

  • Use Dynamic Programming to solve overlapping subproblems.
  • The minimum cost to reach a step is the cost of that step plus the minimum cost of reaching one of the two previous steps.
  • The final result is the minimum cost to reach the last or second last step since you can jump from either directly to the top.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n) (can be optimized to O(1) by using only two variables)

Solution

We use a dynamic programming approach. Define a dp array where dp[i] is the minimum cost required to reach step i. Initialize dp[0] with cost[0] and dp[1] with cost[1] because you can start at either step. For each subsequent step, the recurrence is dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Finally, the answer is the minimum of dp[n-1] and dp[n-2] since you can reach the top from either of these steps. This method efficiently computes the answer in one pass through the array.

Code Solutions

# Python implementation with detailed comments

def minCostClimbingStairs(cost):
    n = len(cost)  # number of steps
    # dp array to store minimum cost to reach each step
    dp = [0] * n
    dp[0] = cost[0]  # cost to start at step 0
    dp[1] = cost[1]  # cost to start at step 1
    
    # Compute minimum cost for each subsequent step
    for i in range(2, n):
        # cost to reach current step is current cost + min cost of the two previous steps
        dp[i] = cost[i] + min(dp[i-1], dp[i-2])
    
    # The top can be reached from the last or second last step
    return min(dp[n-1], dp[n-2])

# Example usage:
cost = [10, 15, 20]
print(minCostClimbingStairs(cost))
← Back to All Questions