动态规划法是分治法的延伸。当用递归法分割出来的问题“一而再，再而三”出现时，就可以运用记忆（Memorization）法来存储这些问题。与分治法不同的地方在于，动态规划法增加了记忆机制的使用，将处理过的子问题的答案记录下来，避免重复计算。
下面我们来看著名的斐波那契数列（Fibonacci Sequence）的求解。斐波那契数列的基本定义如下：
简单来说，这个数列的第0项是0、第1项是1，之后的各项的值是由其前面两项的值相加的结果（后面的每项值都是其前两项值之和）。
前面斐波那契数列是用类似分治法的递归法，如果改用动态规划法，那么已计算过的数据就不必重复计算了，也不会再往下递归，进而达到提高性能的目的。例如我们想求斐波那契数列的第4项数Fib（4），它的递归过程可以用图5-1表示。
图5-1 计算斐波那契数列的递归执行路径图
从上面的执行路径图中，我们可以看到递归调用了9次，而加法运算执行了4次，Fib（1）执行了3次，重复计算影响了执行性能。我们根据动态规划法的算法思路可以绘制出如图5-2所示的执行示意图。
图5-2 采用动态规划法计算斐波那契数列
前面提过动态规划法的精神是已计算过的数据不必重复计算。为了达到这个目的，我们可以先设置一个用来记录该斐波那契数列中的项是否已计算过的数组output，该数组中的每一个元素用来分别记录已被计算过的斐波那契数列中的各项。不过在计算之前，该output数组的初值全部设置为空值（在C语言中，空值为NULL，在Python语言中，空值为None），当该斐波那契数列中的项被计算过后，就必须将该项计算得到的值存储到output数组中。举例来说，我们可以将F（0）记录到output[0]，F（1）记录到output[2]，以此类推。
每当要计算斐波那契数列中的项时，就先从output数组中判断，如果是空值，就进行计算，再将计算得到的斐波那契数列项存储到对应的output数组中（数组下标对应数列的项次），这样就可以确保斐波那契数列的每一项只被计算过一次。算法的执行过程如下：
（1）第一次计算F（0），按照斐波那契数列的定义，得到数值为0，将此值存入用来记录已计算斐波那契数列的数组中，即output[0]=0。
（2）第一次计算F（1），按照斐波那契数列的定义，得到数值为1，将此值存入用来记录已计算斐波那契数列的数组中，即output[1]=1。
（3）第一次计算F（2），依照斐波那契数列的定义，得到数值为F（1）+F（0），因为这两个数值都已计算过，因此可以直接计算output[1]+output[0]=1+0=1，将此值存入用来记录已计算斐波那契数列的数组中，即output[2]=1。
（4）第一次计算F（3），按照斐波那契数列的定义，得到数值为F（2）+F（1），因为这两个数值都已计算过，因此可以直接计算output[2]+output[1]=1+1=2，将此值存入用来记录已计算斐波那契数列的数组中，即output[3]=2。
（5）第一次计算F（4），按照斐波那契数列的定义，得到数值为F（3）+F（2），因为这两个数值都已计算过，因此可以直接计算output[3]+output[2]=2+1=3，将此值存入用来记录已计算斐波那契数列的数组中，即output[4]=3。
（6）第一次计算F（5），按照斐波那契数列的定义，得到数值为F（4）+F（3），因为这两个数值都已计算过，所以可以直接计算output[4]+output[3]=3+2=5，将此值存入用来记录已计算斐波那契数列的数组中，即output[5]=5，后续各项以此类推。
