使用斐波那契数列来分析动态规划算法

对于动态规划，可以将其理解为把一个原始的问题分解成为很多歌规模相对较小的子问题，对于每一个子问题之间是存在一定的联系的，而通过对各个子问题的求解，并将这些求解组合起来就可以得到原始问题的解。

这里主要是通过使用斐波那契数列的求解来对动态规划算法的几要素进行分析。

对于斐波那契函数的算法主要提供两种算法，一种是递归算法，另外一种是动态规划算法。

首先是对于动态规划算法的四个要素进行一个说明，动态规划算法用于解决的原始问题有四个基本元素，分别是最优子结构、重叠子问题、状态与状态转移方程以及边界条件。一个问题具有最优子结构即该问题的最优解必然会包含它的子问题的最优解，举个例子就是如果爬楼，我们想要知道有什么方式可以爬到顶楼，而我们知道了可以用什么方式爬次顶楼，还有次顶楼的下一楼的方式爬上去之后，我们就可以知道有那些方法区爬顶楼，这也就是对于爬顶楼的子问题，就是如何去爬次顶楼。

第二个元素就是重叠子问题。对于具有子结构的问题会让人想到把各个子问题相互独立，所以会考虑递归算法，但是对于递归算法的运行过程中，会存在很多的重复性的计算，这也就导致了效率的降低，所以在使用动态规划算法时，对于要解决的原始问题中，已经解决了子问题的结果是可以直接取用的，无需再次去计算。

第三个元素是动态规划算法的核心，就是状态与状态转移方程，对于状态即是原始问题的子问题的解，而状态转移方程就是找到子问题之间的递推关系，有了递推关系和子问题的解，就可以从最底部开始，一直往上解决子问题，直至解决了原始问题。通过这个元素就可以实现只解决一次各个子问题，就可以一次性的获得原始问题解。

最后一个就是边界条件。对于边界条件也即是运行程序的终止条件，这个条件也就是原始问题的规模参数，当达到了这个边界条件时就可以停止并得到原始问题的解。

以下是以递归算法求斐波那契数列：

def fib1(n):
    print('fib(',n,")")
    if n<1:
        return 0
    if n<3:
        return 1
    return fib1(n-1)+fib1(n-2)

添加图片注释，不超过 140 字（可选）

以下是动态规划算法求斐波那契数列：

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

print(fib2(5))

添加图片注释，不超过 140 字（可选）

对于使用递归算法求解时随着求解的值逐渐增大递归中出现了大量的重复计算，这也导致了时间复杂度急剧变大运行的效率会逐渐降低，其时间复杂度为O(n^2)。

而使用动态规划算法的时间复杂度仅为O(n)。但是想对的动态规划算法需要额外的内存空间，空间复杂度会相对较高，因此动态规划算法是使用空间复杂度高来换取低时间复杂度的算法。