## Similar Problems

Similar Problems not available

# Min Cost Climbing Stairs - Leetcode Solution

LeetCode: Min Cost Climbing Stairs Leetcode Solution

Difficulty: Easy

Topics: dynamic-programming array

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`

.

## Min Cost Climbing Stairs Solution Code

`1`