You can climb 1 or 2 steps at a time. How many different ways can you climb to the top of the building?
Note: the given n is a positive integer.
Example 1:
Example 2:
I actually thought about permutation and combination at the beginning. Because I lost mathematics for some years, I went to turn over the formula again and struggled for a long time, but I was still at a loss.
Then I read the prompt and said that I had considered all the previous steps before I suddenly realized that recursion was available.
Because, if you have climbed N floors and used M methods, if you can only take one step on the basis of this status quo, then there are only M possibilities at this time, that is, you can only take one step;
Does that mean there are 2m possibilities to climb the n+ 1 layer?
That's not true, because the situation mentioned above is that you can't change the previous step after walking n floors. However, when climbing the n- 1 floor, if there are two floors to go, you can have the option of climbing 1 steps.
Then, suppose there are O possibilities when climbing n- 1 layer, and then climb the second step to reach n+ 1.
So the possibility of climbing the n+ 1 layer is m+o.
That is to say:
In addition, you can't write simple recursive formulas, which will lead to a lot of repeated calculations. Using a dictionary to store the calculation results here can reduce the number of calculations.