# Day 7: Min Cost Climbing Stairs

*Problem Link:*

*Problem Statement:*

You are given an integer array `cost`

where `cost[i]`

is the cost of `ith`

step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index `0`

, or the step with index `1`

.

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

*Example 1:*

**Input:** cost = [10,15,20]

**Output:** 15

**Explanation:** Cheapest is: start on cost[1], pay that cost, and go to the top.

*Example 2:*

**Input:** cost = [1,100,1,1,1,100,1,1,100,1]

**Output:** 6

**Explanation:** Cheapest is: start on cost[0], and only step on 1s, skipping cost[3].

*Constraints:*

`- 2 <= cost.length <= 1000`

- 0 <= cost[i] <= 999

*My Solution:*

`class Solution:`

def minCostClimbingStairs(self, cost: List[int]) -> int:

for i in range(len(cost) - 3, -1, -1):

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

return min(cost[0], cost[1])

*Explanation:*

This is **top-down dynamic programming** (**DP**) approach solution. We can think of this as the build-up of a number of smaller subproblems, starting at the end.

At each step, we can consider the answer to be the combined **cost** of the current step, plus the lesser result of the total **cost** of each of the solutions starting at the next two steps. This means that by thinking backward, we can solve the smallest problem first, and then build down from there.

For the last two steps, the answer is clearly their individual **cost**. For the third to last step, it’s that step’s **cost**, plus the lower of the last two steps. Now that we know that, we can store that data for later use at lower steps. Normally, this would call for a DP array, but in this case, we could simply store the values **in place**.

*(**Note**: If we choose to not modify the input, we could create a DP array to store this information at the expense of **O(N) extra space**.)*

So we should iterate downward from the end, starting at the third step from the end, and update the values in **cost[i]** with the best total **cost** from **cost[i]** to the end. Then, once we reach the bottom of the steps, we can choose the best result of **cost[0]** and **cost[1]** and **return** our answer.

*Time Complexity: O(N)**where**N**is the length of**cost**Space Complexity: O(1)**or**O(N)**if we use a separate DP array*

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!