Here's a coding challenge:

**Imagine you have n 2x1 bricks. How many different ways can those bricks be stacked to cover an nx2 area?**

Stop! Take a second to think about the problem and come up with a solution before reading further!

## Solution

On first learning about the challenge, I immediately thought about dynamic programming and recursion. The base cases are:

- when
*n*= 0, there is 1 way (0 bricks) - when
*n*= 1, there is 1 way (1 horizontal brick)

However, I couldn't see the recursive step and turned to visualizations of the stacks for the next few values of *n* to try and find a pattern:

As *n* grows, the number of different stacks is 1, 1, 2, 3, 5, 8... the Fibonacci sequence! That was simpler than anticipated. But while coding the solution had become significantly simpler, I still didn't have a strong intuition for the recursive step. To build that intuition, I color-coded the *n*-2 and *n*-1 cases for a couple of values of *n* and then showed how the new stacks are built off of them:

Great! Recursive step finally understood.

And just for the sake of completion, here's a coded solution in Python that's even memoized:

```
from functools import cache
@cache
def stack(n):
if n < 2:
return 1
else:
return stack(n-1) + stack(n-2)
```