> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/algorithms/dynamic-programming ]
> [project group:: Neetcode 150]
> [difficulty:: easy]
> [status:: done]
> [link:: https://leetcode.com/problems/min-cost-climbing-stairs/]
> [up:: [[Leetcode MOC]]]
> [same:: [[70. Climbing Stairs]]]
<!--ID: 1677121825026-->
## Problem
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:** You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
**Example 2:**
**Input:** cost = [1,100,1,1,1,100,1,1,100,1]
**Output:** 6
**Explanation:** You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
**Constraints:**
- `2 <= cost.length <= 1000`
- `0 <= cost[i] <= 999`
## Solution
### Mine
#### Python
```python
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
cost.extend([0,0])
for i in range(len(cost) - 3, -1, -1):
cost[i] += min(cost[i + 1], cost[i + 2])
return min(cost[0], cost[1])
```
Beat 96.28% in runtime and 96.63% in memory
We actually only need to add one 0 and start from the second to last item in the list:
```python
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
cost.append(0)
for i in range(len(cost) - 3, -1, -1):
cost[i] += min(cost[i + 1], cost[i + 2])
return min(cost[0], cost[1])
```
#### Neetcode
Same solution
### LC's
## Things I Learned
### Neetcode Notes
![[Pasted image 20230124205151.png]]
The height of the tree is $n$ (size of array), and since there are two branches at each item at each level, the time complexity would be $O(2^n)$ if brute forced.
If you remove repeated work, it becomes $O(n)$. This is because there are $n$ subproblems if you cache the repeated work: one for each position of the array.
#### DP Approach
Solve from right of array then move backwards - start at base case then solve next subproblem from position to left. This is the same as we did in [[70. Climbing Stairs]].
At index 3, since it doesn't exist, put default value of 0
From index 2 to out of bounds, 20
From index 1: single jump is 15 + 20 (above subproblem); double jump is just 15; min is 15 replace value in list with that
From index 0: 10 + one jump (15), or 10 + two jump (20) , min is 25, replace value in list with that (or just use a separate variable so you don't have to overwrite)
![[Pasted image 20230124205808.png]]
Then return the minimum of first two items in list.
Time complexity: $O(n)$; memory complexity $O(1)$.
## Scratchpad