Python代码

class Solution(object):
    dic = {0:0,1:1}

    def Fibonacci(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n in self.dic:
            return self.dic[n]
        self.dic[n] = self.Fibonacci(n-1) + self.Fibonacci(n-2)
        return self.dic[n]

主要是递归的话大部分数据需要计算两遍，可以计算的时候储存到dictionary 第二次就直接取就好