談到動(dòng)態(tài)規(guī)劃，很多人會(huì)疑惑動(dòng)態(tài)規(guī)劃難嗎？說(shuō)實(shí)話很難，特別是對(duì)于初學(xué)者來(lái)說(shuō)，入門動(dòng)態(tài)規(guī)劃的時(shí)候，舉個(gè)例子，看 0-1背包問(wèn)題，很容易就被題目弄懵了。就算看的懂答案，但就是自己不會(huì)做，不知道怎么下手。就像做遞歸的題，看的懂答案，但下不了手。

對(duì)于動(dòng)態(tài)規(guī)劃，好多題都會(huì)用到，如果你對(duì)動(dòng)態(tài)規(guī)劃感興趣，或者你不知道怎么下手，那么這篇文章的將會(huì)系統(tǒng)的介紹什么是動(dòng)態(tài)規(guī)劃，幫助大家做題。

為了兼顧初學(xué)者，我會(huì)從最簡(jiǎn)單的題講起，后面會(huì)越來(lái)越難，最后面還會(huì)講解，該如何優(yōu)化。因?yàn)?80% 的動(dòng)規(guī)都是可以進(jìn)行優(yōu)化的。不過(guò)我得說(shuō)，如果你連動(dòng)態(tài)規(guī)劃是什么都沒(méi)聽(tīng)過(guò)，可能這篇文章你也會(huì)壓力山大。

一、什么是動(dòng)態(tài)規(guī)劃?

動(dòng)態(tài)規(guī)劃算法是新手在剛接觸算法設(shè)計(jì)時(shí)很苦惱的問(wèn)題，有時(shí)候覺(jué)得難以理解，但是真正理解之后，就會(huì)覺(jué)得動(dòng)態(tài)規(guī)劃其實(shí)并沒(méi)有想象中那么難。

動(dòng)態(tài)規(guī)劃(Dynamic Programming)是一種分階段求解決策問(wèn)題的數(shù)學(xué)思想，它通過(guò)把原問(wèn)題分解為簡(jiǎn)單的子問(wèn)題來(lái)解決復(fù)雜問(wèn)題，動(dòng)態(tài)規(guī)劃在很多領(lǐng)域都有著廣泛的應(yīng)用,例如管理學(xué)，經(jīng)濟(jì)學(xué)，數(shù)學(xué)，生物學(xué)，等等。

（1）動(dòng)態(tài)規(guī)劃適用于解決帶有最優(yōu)子結(jié)構(gòu)和子問(wèn)題重疊性質(zhì)的問(wèn)題

1. 最優(yōu)子結(jié)構(gòu) : 即是局部最優(yōu)解能夠決定全局最優(yōu)解(也可以認(rèn)為是問(wèn)題可以被分解為子問(wèn)題來(lái)解決),如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，我們就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

2. 子問(wèn)題重疊 : 即是當(dāng)使用遞歸進(jìn)行自頂向下的求解時(shí),每次產(chǎn)生的子問(wèn)題不總是新的問(wèn)題,而是已經(jīng)被重復(fù)計(jì)算過(guò)的問(wèn)題.動(dòng)態(tài)規(guī)劃利用了這種性質(zhì),使用一個(gè)集合將已經(jīng)計(jì)算過(guò)的結(jié)果放入其中,當(dāng)再次遇見(jiàn)重復(fù)的問(wèn)題時(shí),只需要從集合中取出對(duì)應(yīng)的結(jié)果。

（2）動(dòng)態(tài)規(guī)劃與分治算法的區(qū)別

相信了解過(guò)分治算法的同學(xué)會(huì)發(fā)現(xiàn)，動(dòng)態(tài)規(guī)劃與分治算法很相似，下面我們例舉出一些它們的相同之處與不同之處。

相同點(diǎn)：

1. 分治算法與動(dòng)態(tài)規(guī)劃都是將一個(gè)復(fù)雜問(wèn)題分解為簡(jiǎn)單的子問(wèn)題。

2. 分治算法與動(dòng)態(tài)規(guī)劃都只能解決帶有最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題。

不同點(diǎn)：

1. 分治算法一般都是使用遞歸自頂向下實(shí)現(xiàn)，動(dòng)態(tài)規(guī)劃使用迭代自底向上實(shí)現(xiàn)或帶有記憶功能的遞歸實(shí)現(xiàn)。

2. 動(dòng)態(tài)規(guī)劃解決帶有子問(wèn)題重疊性質(zhì)的問(wèn)題效率更加高效。

3.分治算法分解的子問(wèn)題是相對(duì)獨(dú)立的。

4. 動(dòng)態(tài)規(guī)劃分解的子問(wèn)題是互相帶有關(guān)聯(lián)且有重疊的。

（3）斐波那契數(shù)列

斐波那契數(shù)列就很適合使用動(dòng)態(tài)規(guī)劃來(lái)求解，它在數(shù)學(xué)上是使用遞歸來(lái)定義的,公式為F(n) = F(n-1) + F(n-2)

斐波那契數(shù)列求解過(guò)程

普通遞歸實(shí)現(xiàn)

一個(gè)最簡(jiǎn)單的實(shí)現(xiàn)如下：

    public int fibonacci(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
 
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

但這種算法并不高效，它做了很多重復(fù)計(jì)算，它的時(shí)間復(fù)雜度為O(2^n)。

動(dòng)態(tài)規(guī)劃遞歸實(shí)現(xiàn)

使用動(dòng)態(tài)規(guī)劃來(lái)將重復(fù)計(jì)算的結(jié)果具有"記憶性"，就可以將時(shí)間復(fù)雜度降低為O(n)。

    public int fibonacci(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
 
        // 判斷當(dāng)前n的結(jié)果是否已經(jīng)被計(jì)算,如果map存在n則代表該結(jié)果已經(jīng)計(jì)算過(guò)了
        if (map.containsKey(n))
            return map.get(n);
 
        int value = fibonacci(n - 1) + fibonacci(n - 2);
        map.put(n, value);
        return value;
    }

雖然降低了時(shí)間復(fù)雜度，但需要維護(hù)一個(gè)集合用于存放計(jì)算結(jié)果，導(dǎo)致空間復(fù)雜度提升了。

動(dòng)態(tài)規(guī)劃迭代實(shí)現(xiàn)

通過(guò)觀察斐波那契數(shù)列的規(guī)律，發(fā)現(xiàn)n只依賴于前2種狀態(tài)，所以我們可以自底向上地迭代實(shí)現(xiàn)。

    public int fibonacci(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
 
        // 使用變量a,b來(lái)保存上次迭代和上上次迭代的結(jié)果
        int a = 1;
        int b = 2;
        int temp = 0;
 
        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
 
        return temp;
    }

這樣不僅時(shí)間復(fù)雜度得到了優(yōu)化，也不需要額外的空間復(fù)雜度。