Prompt: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps at a time. How many ways can you climb to the top?

Example:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution: This is a simple top down memorization DP solution. We know that there are 2 available ways to climb, 2 steps or 1 step. When using the top down approach, we can climb down the stairs from n to 0. If n-2 > 0 then you can climb the steps in 1 way. If n-1 > 0 then you can also climb the steps in 1 way. The total number of ways that you can climb at each step is the multiple of the number of ways you can climb from the previous steps and the number of ways that you can climb down from the current step.