leetcode Of the 70 topic climb stairs
Suppose you're climbing the stairs . need n You can reach the top of the building .
Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？
Example 1：
Input ：n = 2
Output ：2
explain ： There are two ways to climb to the top .
1. 1 rank + 1 rank
2. 2 rank
Example 2：
Input ：n = 3
Output ：3
explain ： There are three ways to climb to the top .
1. 1 rank + 1 rank + 1 rank
2. 1 rank + 2 rank
3. 2 rank + 1 rank
Tips ：
1 <= n <= 45
Climb to the top of the building. From the perspective of reverse thinking , It can be understood as coming down from the roof , You can only go down one or two floors at a time , With n=6 For example , First, we have two ways to go , Or go down 5 floor , Or go down 4 floor , So from 6 The problem of the number of methods downstairs is solved from 5 The number of ways downstairs + from 4 The number of ways downstairs , So the scale of the problem is reduced , To find inspiration for recursion .
The following figure shows the conditions for exiting recursion , When on the first floor , Just one way , On the second floor , Yes 1+1,2 These two methods .
Through the top-down solution, we get 6 The number of ways downstairs .
# python3
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
return Solution.climbStairs(self,n-1)+Solution.climbStairs(self,n-2)
But there was a timeout error , So we need to improve 
We continue to look for clues from this picture
But we calculate 6 How to go downstairs , It can be transformed into seeking from 5 Floor and 4 How to go downstairs , however , Calculate from 5 How to go downstairs , We have calculated 4 How to go downstairs , But then I put 4 The method of going downstairs has been calculated , And the more at the bottom of the tree , The more repeated calculations . A lot of time was wasted .
therefore , Found a place to optimize .
You can store the repeatedly calculated values first , When you encounter it again, you will directly call , You can use hash map For storage , stay python in , You can use a dictionary to hash map The implementation of the .
# python3
''' In the process of recursive execution, many things are calculated repeatedly , Wasted time If f(k) Calculated , You can save values to hash map in Meet again f(k) Direct weight hash map Call in python Available in dict Realization hash map The function of '''
class Solution1:
hash_map = dict()
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
if None != self.hash_map.get(n):
return self.hash_map.get(n)
else:
result = Solution.climbStairs(self,n-1)+Solution.climbStairs(self,n-2)
self.hash_map[n] = result
Successfully passed the test 
Recursive method can be used to solve from top to bottom , So is it non recursive .
Review this picture again
f(1)+f(2) Got it f(3)
and f(4)=f(3)+f(2)
after f(5)=f(4)+f(3)
Finally get f(6)=f(5)+f(4)
Store intermediate results between two variables , The final result can be obtained by continuously updating and accumulating
# python3
''' Non recursive methods , Use the cycle , Bottom up accumulation '''
class Solution2:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
result = 0
temp1 = 2
temp2 = 1
for i in range(3,n+1):
result = temp1 + temp2
temp2 = temp1
temp1 = result
return result
Successfully passed the test , And the time complexity of the loop is O(n), Passing time is really shorter than recursion .
