Minimum Cost Climbing Stairs

December 20, 2023

Problem #

Given an array of integers, find the minimum cost to reach the top of the stairs. Each step costs some amount as described in the input array. You can either climb one or two steps at a time.

Solution #

To solve the problem “Given an array of integers, find the minimum cost to reach the top of the stairs, where each step costs a certain amount and you can climb one or two steps at a time,” we can use dynamic programming. The idea is to build up a solution by finding the minimum cost to reach each step, starting from the bottom of the stairs.

Here’s how you can implement it in Python:

def minCostClimbingStairs(cost):
    n = len(cost)
    if n == 0:
        return 0
    if n == 1:
        return cost[0]

    # dp[i] will hold the minimum cost to reach step i
    dp = [0] * n

    # The cost of reaching the first two steps is the cost of the steps themselves
    dp[0], dp[1] = cost[0], cost[1]

    # Build the dp array
    for i in range(2, n):
        # For each step, you can come from one step before or two steps before
        # Choose the one with the minimum cost
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

    # The minimum cost to reach the top can be from either the last step or the second to last step
    return min(dp[-1], dp[-2])

# Example usage
cost = [10, 15, 20]
print(minCostClimbingStairs(cost))  # Output: 15

In this solution:

• The dp array is used to store the minimum cost to reach each step.
• The cost to reach the first two steps is directly the cost of those steps.
• For each subsequent step, the cost is calculated as the cost of that step plus the minimum cost of reaching either of the two previous steps.
• Finally, since you can reach the top from either the last step or the second to last step, we return the minimum of these two values.