Lifting possibilities n stairs with restrictions on the 20th floor

Question

Im solving the recursion problem, in which the int stairs (int n) function returns the number of possibilities when climbing stairs to n, provided that either 1 step or 2 steps is performed. The following code solves the following:

int stairs(int n) { if (n<0) return 0; if (n==0) return 1; return stairs(n-1) + stairs(n-2); } 

Now I have a limitation that says: if you reach the 20th floor, you MUST use an elevator that automatically takes you to the nth floor. If for some reason you miss level 20 (for example, go to level 19, and then go up 2 floors to level 21), continue as usual. Find the number of possibilities to limit above. What i have done so far:

 int stairs20(int n) { if (n<=20) return stairs(n); return stairs(20) + stairs(n-21); } 

The logic of the code is to calculate the number of opportunities to reach the 20th floor and the number of opportunities from the 21st floor and above. I believe that this does not return the correct answer and would be grateful for advice on where my mistake is or what I do not expect?

Answer 1

When n>20 ,

• you can first reach the 20th floor, then go all the way up => stairs(20)

• you can also get to the 19th floor, then go to the 21st floor, from the 21st floor, you have stairs(n-21) paths to floor n, so => stairs(19)*stairs(n-21)

So, summarize this stairs(20) + stairs(19) * stairs(n-21) .

You can use dynamic programming to avoid calculating the same value.

Answer 2

The main recursion scheme is as follows

 int stairs(unsigned int n) { if (n < 2) return 1; return stairs(n-1) + stairs(n-2); } 

Now the question you need to ask yourself is, as a rule, applied to stairs 20, will change the recursion scheme? If n > 20 , then stairs(n) will be equal to stairs(20) + <number_of_ways_to_climb_to_n_without_reaching_floor20) . How do you avoid sex 20? When you reach floor 19 and go straight to floor 21. Then, on floor 21, you must rise until you reach the floor. Thus, stairs(19)*stairs(n-21) reaches floor n without stopping at floor 20.

Therefore, the final answer:

 int stairs20(unsigned int n) { if(n > 20) { return stairs(20) + stairs(19)*stairs(n-21); } else { return stairs(n); } }