七、动态规划

记录一下对动态规划的学习。在学习数据结构与算法的过程中，觉得比较难的一个算法思想就是动态规划了。它的应用实在是多，比如在机器学算法CRF中，就用到了动态规划。

一、斐波那契数列

下面就以斐波那契数列来说明动态规划把。我们都知道斐波那契数列的递推公式是

这个公式在高中就可以求通项公式，不过求解的过程在当时还是有点点麻烦，而现在来说的话，我们都是采用程序来解决这个问题。
思路一：采用递归调用的方式来解决。这种方式采用起来很简单。但是当n很大的时候，时间复杂度就是指数级的增长了。
时间复杂度：O(2^n)

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

if __name__ == '__main__':
    print(fib(0))  # 0
    print(fib(1))  # 1
    print(fib(2))  # 1
    print(fib(3))  # 2
    print(fib(4))  # 3
    print(fib(5))  # 5

之所以出现了指数级的一个时间复杂度，就是因为我们在计算的过程中，进行了很多的重复计算，所以我们能够想到的就是将重复计算出的值进行一个保存，然后后面要用到的时候，就直接进行一个调用就行了。
思路二：采用自顶向下的解决方法，也就是我们常说的记忆化搜索的方式来解决这个问题
思路三：采用自底向上的方式去解决这个问题，这种方法就是我们所说的动态规划。看下面的代码，我们就根据一次的循环遍历得到时间复杂度O(n)，因为是用了空间去换取时间上的优势，那么我们的空间复杂度就是O(n)。由此我们可以看出动态规划将时间复杂大大的降低了

def fib(n):
    if n==0:
        return  0
    alist = [-1] * (n+1)
    alist[0]=0
    alist[1]=1
    for i in range(2,n+1):
        alist[i] = alist[i-1]+alist[i-2]
    return alist[n]

大多数dp问题的本质都是递归问题，在递归的过程中，我们就发现了重叠的子问题（计算重复），对于重叠的子问题，我们可以采用记忆化搜索来解决，它是一种自顶向下的解决问题的手段。另外一种方式就是动态规划，它的的本质其实和记忆化搜索是一样，只不过它是自底向上的方式去解决问题。
和此思想最相关的一个LeetCode 题目就是LeetCode 70，就是将爬楼梯的问题仔细思考之后，本质还是一个斐波那契数列。

二、动态规划

这部分的总结，有不少感悟来自于知乎大神答案的总结，喜欢的话，就直接去后面的链接看看。

2.1、本质

• 动态规划的本质：对问题的定义和状态转移方程的定义。
  通过定义好问题和状态转移方程，就能够很好的将问题拆分出来，从而写出递推的公式，进而解决问题。就像是解决递归问题，要找到递归终止条件（最基本的同一问题）和递归的过程条件。

2.2、递归、贪心、搜索和动态规划

算法	理解
递归
贪心
搜索
动态规划

持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
二、数组及LeetCode典型题目分析
三、链表（Linked list）以及LeetCode题
四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
七、动态规划
八、排序与搜索
九、哈希表
参考资料：
1、https://www.zhihu.com/question/23995189/answer/613096905