1.为什么备忘录法和动态规划法：

斐波那契是很多人入门递归思想的第一课，所以很多人都会最简单的一种递归写法，但是其实递归的过程，他的时间复杂度非常高，达到了O(2的n次方)这样的一个指数级别。
先看最简单的：

# 1.最普通的递归算法，时间复杂度为O(2的n次方)
class Solution:
    def fib(self, n):
        if n == 1 or n == 2:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)

上述代码非常好写，但是时间复杂度高，你试一个n为100可能就要算很久。这是为什么呢？主要是因为这里有很多的重复计算：
我学习这个的途径动态规划详解

import time


# 1.最普通的递归算法，时间复杂度为O(2的n次方)
class Solution:
    def fib(self, n):
        if n == 1 or n == 2:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)


# 2.带备忘录的斐波那契数列， 时间复杂度为 O(n)
class Solution2:

    def fib(self, n):
        help_dict = {1: 1, 2: 2}
        return self.helper(n, help_dict)

    def helper(self, n, help_dict):
        if n == 1 or n == 2:
            return 1
        if n in help_dict:
            return help_dict[n]
        else:
            help_dict[n] = self.helper(n - 1, help_dict) + self.helper(n - 2, help_dict)
            # print(help_dict)
            return self.helper(n - 1, help_dict) + self.helper(n - 2, help_dict)


# 3.动态规划，时间复杂度为O(n)
class Solution3:

    def fib(self, n):
        if n == 1 or n == 2:
            return 1
        result = {1: 1, 2: 1}
        for i in range(3, n + 1):
            result[i] = result[i - 1] + result[i - 2]
        return result[n]


s = Solution()
start = time.time()
print(s.fib(30))
end_1 = time.time()
print("普通的斐波那契数列，简单的采用递归所需时间 :{}".format(end_1 - start))

s2 = Solution2()
print(s2.fib(30))
end_2 = time.time()
print("采用备忘录需要的时间 :{}".format(end_2 - end_1))

s2 = Solution2()
print(s2.fib(30))
print("采用动态规划需要的时间：{}".format(time.time() - end_2))