Current location - Training Enrollment Network - Mathematics courses - Recursive method-Climbing stairs (simple)
Recursive method-Climbing stairs (simple)
Suppose you are climbing stairs. It takes n steps to get to the roof.

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.