## Recursion vs. Dynamic Programming Using a Question from AMC8

Here is an example from 2010 AMC8 Question $$25$$ (American Mathmatical Competition):

Everyday at school, Jo climbs a flight of $$6$$ stairs. Jo can take the stairs $$1$$, $$2$$, or $$3$$ at a time. For example, Jo could climb $$3$$, then $$1$$, then $$2$$. In how many ways can Jo climb the stairs?

$\textbf{(A)}\ 13 \qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 20\qquad\textbf{(D)}\ 22\qquad\textbf{(E)}\ 24$

### Recursion

This mathmatical question can be easily solved using the following python recursion code:

But, what if there is a quicker way? Let’s try using dynamic progamming.

### Dynamic Programming

We can start with $$\text{step}_1$$ as the last step, $$\text{step}_2$$ as the second to last step, and $$\text{step}_3$$ as the third to last step. According to the recursion code, if $$x$$ is the current step, we have $$\text{step}_x = \text{step}_{x-1} + \text{step}_{x- 2} + \text{step}_{x - 3}.$$

Writing it in the dynamic programming way, we get

which runs much faster than recusion.