## References

functools — Higher-order functions and operations on callable objects

## Cache

### Fibonacci Number

509. Fibonacci Number

#### Recursion

As you can see, recursion is very slow since each step it calculates the pervious step again.

#### Top-Down Approach using Memoization

The above cache solution is the same as this one, the implementation of Memoization.

### Staircase

70. Climbing Stairs

### Staircase II

Suppose there is a staircase that you can climb in either 1 step, 2 steps, or 3 steps. In how many possible ways can you climb the staircase if the staircase has n steps? Write a recursive function to solve the problem.

Example:

• n == 1 then answer = 1

• n == 3 then answer = 4

The output is 4 because there are four ways we can climb the staircase:

• 1 step + 1 step + 1 step
• 1 step + 2 steps
• 2 steps + 1 step
• 3 steps
• n == 5 then answer = 13