記錄一下對(duì)動(dòng)態(tài)規(guī)劃的學(xué)習(xí)。在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的過(guò)程中，覺(jué)得比較難的一個(gè)算法思想就是動(dòng)態(tài)規(guī)劃了。它的應(yīng)用實(shí)在是多，比如在機(jī)器學(xué)算法CRF中，就用到了動(dòng)態(tài)規(guī)劃。

一、斐波那契數(shù)列

下面就以斐波那契數(shù)列來(lái)說(shuō)明動(dòng)態(tài)規(guī)劃把。我們都知道斐波那契數(shù)列的遞推公式是

這個(gè)公式在高中就可以求通項(xiàng)公式，不過(guò)求解的過(guò)程在當(dāng)時(shí)還是有點(diǎn)點(diǎn)麻煩，而現(xiàn)在來(lái)說(shuō)的話，我們都是采用程序來(lái)解決這個(gè)問(wèn)題。
思路一：采用遞歸調(diào)用的方式來(lái)解決。這種方式采用起來(lái)很簡(jiǎn)單。但是當(dāng)n很大的時(shí)候，時(shí)間復(fù)雜度就是指數(shù)級(jí)的增長(zhǎng)了。
時(shí)間復(fù)雜度：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

之所以出現(xiàn)了指數(shù)級(jí)的一個(gè)時(shí)間復(fù)雜度，就是因?yàn)槲覀冊(cè)谟?jì)算的過(guò)程中，進(jìn)行了很多的重復(fù)計(jì)算，所以我們能夠想到的就是將重復(fù)計(jì)算出的值進(jìn)行一個(gè)保存，然后后面要用到的時(shí)候，就直接進(jìn)行一個(gè)調(diào)用就行了。
思路二：采用自頂向下的解決方法，也就是我們常說(shuō)的記憶化搜索的方式來(lái)解決這個(gè)問(wèn)題
思路三：采用自底向上的方式去解決這個(gè)問(wèn)題，這種方法就是我們所說(shuō)的動(dòng)態(tài)規(guī)劃?？聪旅娴拇a，我們就根據(jù)一次的循環(huán)遍歷得到時(shí)間復(fù)雜度O(n)，因?yàn)槭怯昧丝臻g去換取時(shí)間上的優(yōu)勢(shì)，那么我們的空間復(fù)雜度就是O(n)。由此我們可以看出動(dòng)態(tài)規(guī)劃將時(shí)間復(fù)雜大大的降低了

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]

大多數(shù)dp問(wèn)題的本質(zhì)都是遞歸問(wèn)題，在遞歸的過(guò)程中，我們就發(fā)現(xiàn)了重疊的子問(wèn)題（計(jì)算重復(fù)），對(duì)于重疊的子問(wèn)題，我們可以采用記憶化搜索來(lái)解決，它是一種自頂向下的解決問(wèn)題的手段。另外一種方式就是動(dòng)態(tài)規(guī)劃，它的的本質(zhì)其實(shí)和記憶化搜索是一樣，只不過(guò)它是自底向上的方式去解決問(wèn)題。
和此思想最相關(guān)的一個(gè)LeetCode 題目就是LeetCode 70，就是將爬樓梯的問(wèn)題仔細(xì)思考之后，本質(zhì)還是一個(gè)斐波那契數(shù)列。

二、動(dòng)態(tài)規(guī)劃

這部分的總結(jié)，有不少感悟來(lái)自于知乎大神答案的總結(jié)，喜歡的話，就直接去后面的鏈接看看。

2.1、本質(zhì)

• 動(dòng)態(tài)規(guī)劃的本質(zhì)：對(duì)問(wèn)題的定義和狀態(tài)轉(zhuǎn)移方程的定義。
  通過(guò)定義好問(wèn)題和狀態(tài)轉(zhuǎn)移方程，就能夠很好的將問(wèn)題拆分出來(lái)，從而寫(xiě)出遞推的公式，進(jìn)而解決問(wèn)題。就像是解決遞歸問(wèn)題，要找到遞歸終止條件（最基本的同一問(wèn)題）和遞歸的過(guò)程條件。

2.2、遞歸、貪心、搜索和動(dòng)態(tài)規(guī)劃

持續(xù)更新中...
數(shù)據(jù)結(jié)構(gòu)與算法系列博客：
一、數(shù)據(jù)結(jié)構(gòu)與算法概述
二、數(shù)組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊(duì)列（Stack and Queue
五、樹(shù)（Trees）
六、遞歸與回溯算法
七、動(dòng)態(tài)規(guī)劃
八、排序與搜索
九、哈希表
參考資料：
1、https://www.zhihu.com/question/23995189/answer/613096905