题解 | #跳台阶#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
dict={1:1,2:2}
class Solution:
    
    def jumpFloor(self , number: int) -> int:
        # write code here

        if(number in dict):
            return dict[number]
        else:
            dict[number]=Solution.jumpFloor(self,number-1)+Solution.jumpFloor(self,number-2)
        return dict[number]

原来这叫记忆化搜索，既然是联系递归的题还是使用了递归的方法，从大到小进行递归，再从小到大进行回溯。

本题注意点：不要把创建字典的步骤放进递归里，否则会不断重置字典，导致时间复杂度O（2^n）超时，我这里是直接定义成全局变量了