> For the complete documentation index, see [llms.txt](https://interviews.woojiahao.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://interviews.woojiahao.com/problems-guide/dynamic-programming-roadmap/linear-sequence/min-cost-to-climb-stairs.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.