空间换时间的最经典的案例

按照暴力的递归解***超出时间复杂度

需要使用相应的数列遍历存储相关的计算出来的数值

class Solution:
    def Fibonacci(self , n: int) -> int:
        
        if n==1 or n==2:
            return 1
        elif n<=40:
            # 使空间换取时间
            shulei = [0 for i in range(n+1)] # 注意下标的位置
            shulei[0] = 0
            shulei[1] = 1 # 这个才是开始
            for i in range(2,len(shulei)):
                shulei[i] = shulei[i-1] + shulei[i-2]
            # 将每一个数据进行存储，空间换时间
            return shulei[n]
            
            
        # write code here