# Min Cost to Climb Stairs

## Observations

On each step

`n`

, we must incur the cost since we have to decide whether or not to move one or two steps upTo reach step

`n`

, you must move from step`n - 1`

or step`n - 2`

To minimize the cost to reach step

`n`

, we need to minimize the cost it takes to reach it

## Recurrence relation

$dp(n) = \begin{cases}
cost(0), n = 0\\
cost(1), n = 1\\
\min(dp(n-1),dp(n-2)) + cost(n)
\end{cases}$

We can define $dp(n)$ as the minimum cost it takes to climb from step $n$. If we start at the first step, the cost is $cost(0)$ and if we start at the second step, the cost is $cost(1)$. Otherwise, for every step $n$, the cost to climb from it is the cost it took to reach it with the cost of leaving the step.

## Bottom-up

The $n$ state caching optimization can be applied here again, given that each state depends only on the previous 2 states.

Last updated