本节将分析动态规划算法与递归算法相比其优势所在.以斐波那契数列为例来进行说明.

用python实现递归算法代码如下:

def fib(n):if(n<1):return 0if(n<3):return 1return fib(n-1)+fib(n-2)

若采用动态规划排序法,即自底向上看,如果可以在计算fib(5)之前把1~4先计算好,就可以避免递归的重复计算,降低时间复杂度.用python实现动态规划算法:

def fib(n):l = [0,1,1]for i in range(3,n+1):l.append(l[i-1]+l[i-2])return l[n]

由此可见,在解决问题时,递归算法是自顶向下构造函数,而动态排序算法是自底向上的思考与构造程序结构.在时间复杂度和空间复杂度都优于递归算法