Min Cost Climbing Stairs - Leetcode Solution

The Min Cost Climbing Stairs problem on Leetcode is a classic dynamic programming problem. It asks you to determine the minimum cost to climb to the top of a given staircase. The staircase has a certain number of steps, represented as an array of integers. Each element in the array represents the cost to climb that step.

The problem statement specifies that you can take one or two steps at a time, but the cost of each step must be paid regardless of the step size. Therefore, your goal is to find the minimum cost to reach the top of the staircase.

One possible approach to solve this problem is to use dynamic programming. You can create an array dp of the same size as the staircase, where dp[i] represents the minimum cost to reach step i of the staircase. You can initialize dp[0] = 0 and dp[1] = cost[1], since the minimum cost to reach the first step is zero (you're already there) and the minimum cost to reach the second step is the cost of the second step. Alternatively, you could initialize dp[0] = cost[0] and dp[1] = cost[1].

To populate the rest of the dp array, you can use the following recurrence relation:

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

This means that the minimum cost to reach step i is the minimum of the cost to reach step i-1 and the cost to reach step i-2, plus the cost of the current step.

After populating the entire dp array, the minimum cost to reach the top of the staircase will be stored in dp[n-1], where n is the number of steps in the staircase.

Here's the implementation of the algorithm in Python:

def minCostClimbingStairs(cost: List[int]) -> int:
    n = len(cost)
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]
    
    for i in range(2, n):
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        
    return min(dp[n-1], dp[n-2])

Time complexity: O(n), where n is the number of steps in the staircase. You iterate through the entire array once.

Space complexity: O(n), where n is the number of steps in the staircase. You create a dp array of size n.

1