You are given an array cost where cost[i] is the cost of i-th step on a staircase. You can start from either the 0-th step or the 1-st step. Each step can be climbed by paying the cost specified, and you can either climb one step or two steps at a time.

Return the minimum cost to reach the top of the floor.

Function Signature:

from typing import List

def min_cost_climbing_stairs(cost: List[int]) -> int:
    """
    Return the minimum cost to reach the top of the floor.

    Parameters:
    - cost: List of integers representing the cost of each step.

    Returns:
    - int: Minimum cost to reach the top.
    """
    # Your code here

Example:

# Input: cost = [1, 2, 3, 4]
# Output: 4
# Explanation: Start from the 0th step, climb to the 2nd step, and reach the top with a minimum cost of 4.

# Input: cost = [10, 15, 20]
# Output: 15
# Explanation: Start from the 1st step, and climb 2 steps to reach the top with a minimum cost of 15.

# Input: cost = [0, 100]
# Output: 0
# Explanation: Start from the 0th step, and climb 2 steps to reach the top with a minimum cost of 0.

# Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
# Output: 6
# Explanation: Start from the 0th step and climb to the 2nd, 4th, 6th, 7th, and 9th step to reach the top with a minimum cost of 6.

Note:

  • The length of cost will be in the range [2, 1000].
  • Each cost[i] will be an integer in the range [0, 999].

Instructions:

  • Write the min_cost_climbing_stairs function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊