# Climbing Stairs

## Transitions

Observe that for every stair, you can make two decisions:

Climb one step

Climb two steps

## Recurrence tree

## Top-down

Top-down can often be implemented by directly modelling the state transitions

The recurrence relation above looks like this:

## Bottom-up

**Trick: **Re-framing the problem
A way to convert top-down to bottom-up solutions is to **re-frame the problem** in a way that only **restricts your view of the data to a subset**, such as the prefix/suffix/sub-array. Solving this subset gives you the tools to solve larger subsets.
A good way to do this is to ask: "Given index i, how do I use the solutions of 0 to i-1 (prefix) or i+1 to n (suffix) solve for index i?"

## Optimization

From the recurrence relation, we only ever require the previous 2 states, `dp(m - 1)`

and `dp(m - 2)`

to compute `dp(m)`

. So, we can store these 2 states as variables instead of using an array.

Keen observers will notice that this is basically the Fibonacci sequence

Last updated