初级编程通关练习题 #6 – 斐波那契数列和DP算法

斐波那契数列中第N个数值的标准计算方式如下：

def fibonacci(n):
    if n in [0, 1]:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

上面的代码最大的缺陷是运行效率低下，因为存在太多重复计算。现在我们可以借助动态规划算法（Dynamic Programming）的两种方式Dp Tablulation 和 Dp Memoization 来改善上面代码的问题。

输入样例：

N = 70

输出样例：

190392490709135

算法思路：

• DP算法的两种方式都需要使用缓存
• DP Tabulation 是利用循环的方法来从小往大计算目标数值，而DP Memoization则是采用递归的方法从上往下计算目标数值。
• 不管是哪一种方法，每次计算出一个中间数值都需要把它保存到缓存中去，这样下一次需要用到同样的中间数值就可以从缓存中直接提取使用，而不需要再次计算。