# Climbing Stairs

## Transitions

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

Climb one step

Climb two steps

## Recurrence tree

We don't count leaves that end with values where `v > n`

. We can also memoize the results of sub-trees such as `2`

, reducing the computation of the right sub-tree to a $O(1)$ lookup.

## 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?"

By re-framing the problem, we will notice that if we are index $m$ and we have computed the optimal solution for $0..m-1$ (prefix), then we can obtain the optimal solution for $m$ using the following recurrence:

**Trick: **Interpreting recurrence relations**
**Define what $dp(i)$ means and read the recurrence in terms of that definition.
For instance, the above can be interpreted as:
$dp(m)$ is the number of ways to reach step $m$
If $m = 1$, then it means we can only take 1 step to reach it (i.e. 1 way)
If $m = 2$, then we can either take 2x1 step or 1x2 steps to reach it (i.e. 2 ways)
Otherwise, the number of ways to reach step $m$ is by stepping once from $m-1$ or stepping twice from $m-2$

## 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.

**Optimization: **$n$-state caching
If your recurrence relies on a finite number of $n$ states only, we can use $n$ variables to represent these states, removing the need for an array

Keen observers will notice that this is basically the Fibonacci sequence

Last updated