# 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 up
* To 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.

```python
def climb_stairs(costs):
    s1, s2 = costs[0], costs[1]
    for i in range(2, len(costs)):
        s1, s2 = s2, min(s1, s2) + costs[i]
    return min(s1, s2)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://interviews.woojiahao.com/problems-guide/dynamic-programming-roadmap/linear-sequence/min-cost-to-climb-stairs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.