Question

动态规划（Dynamic Programming）

Answer 1

Dynamic Programming ：动态规划分为如下几步：

这种存储计算结果以备再次使用称之为： Memoization （这个词，不知道怎么翻译好）

以斐波那契数列为例来说明：

1、使用递归实现：

这种方法是经典的递归运算。以fib(5)为例，整个求解过程可以拆分为：

我们可以看出，fib(2)被计算三次，fib(3)与fib(1)各被计算2次，时间复杂度为O(2^n)。

2、对递归进行改进

3、脱离递归：

改进之后的算法不再使用递归，时间复杂度依然是O(n)。

对以上三种实现编写测试用例：

无意中在Youtube上看到这段视频，就翻译整理下来与大家共享。