Solution 1: Dynamic Programming

To solve this problem, we can use dynamic programming. We’ll create an array dp to store the minimum cost to reach each step. We’ll initialize dp[0] and dp[1] with the costs of the first two steps. Then, for each subsequent step i, we’ll update dp[i] to be the minimum of dp[i-1] and dp[i-2] plus the cost of the current step cost[i]. Finally, we’ll return the minimum of the last two steps in dp, which represents the minimum cost to reach the top.

Here’s a Python implementation of the min_cost_climbing_stairs function using dynamic programming:

from typing import List

def min_cost_climbing_stairs(cost: List[int]) -> int:
    n = len(cost)

    # Initialize an array to store the minimum cost to reach each step
    dp = [0] * n

    # Base cases
    dp[0] = cost[0]
    dp[1] = cost[1]
    
    # Iterate through the steps starting from the 2nd step
    for i in range(2, n):
        # Calculate the minimum cost to reach the current step
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

    # The minimum cost to reach the top is the minimum of the last two steps
    return min(dp[-1], dp[-2])

# Example usage:
cost = [1, 2, 3, 4]
result = min_cost_climbing_stairs(cost)
print(result)  # Output: 4

cost = [10, 15, 20]
result = min_cost_climbing_stairs(cost)
print(result)  # Output: 15

cost = [0, 100]
result = min_cost_climbing_stairs(cost)
print(result)  # Output: 0

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
result = min_cost_climbing_stairs(cost)
print(result)  # Output: 6

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input array cost. We iterate through the array once to fill the dp array.

Space Complexity:

The space complexity is O(n) as well. We use an additional array dp of size n to store the minimum cost to reach each step.

Solution 2: Lower Space Complexity

We can optimize the space complexity of the solution by using two variables to represent the minimum costs for the previous two steps instead of maintaining an entire array. This approach reduces the space complexity from O(n) to O(1).

from typing import List

def min_cost_climbing_stairs(cost: List[int]) -> int:
    # Initialize variables to represent minimum costs for the previous two steps
    prev1 = cost[0]
    prev2 = cost[1]
    
    # Iterate through the array starting from the third step
    for i in range(2, len(cost)):
        # Calculate the minimum cost to reach the current step
        curr_min_cost = min(prev1, prev2) + cost[i]
        
        # Update prev1 and prev2 for the next iteration
        prev1, prev2 = prev2, curr_min_cost
    
    # Return the minimum of the last two steps
    return min(prev1, prev2)

# Example usage:
print(min_cost_climbing_stairs([1, 2, 3, 4]))  # Output: 4
print(min_cost_climbing_stairs([10, 15, 20])) # Output: 15
print(min_cost_climbing_stairs([0, 100]))    # Output: 0
print(min_cost_climbing_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # Output: 6

Explanation:

  • We initialize prev1 and prev2 to represent the minimum costs for the first two steps.
  • We iterate through the array starting from the third step and calculate the minimum cost to reach each step.
  • At each step, we update prev1 and prev2 accordingly.
  • Finally, we return the minimum of the last two steps, which represents the minimum cost to reach the top.

Time Complexity:

The time complexity remains O(n), where n is the length of the input array cost, as we still iterate through the array once.

Space Complexity:

The space complexity is O(1) since we only use a constant amount of extra space to store the previous two minimum costs.