動(dòng)態(tài)規(guī)劃（Dynamic Programming）虎锚，簡(jiǎn)稱DP硫痰，這個(gè)名字給人的感覺(jué)是一種非常高大上非常復(fù)雜的算法，很多同學(xué)看到這個(gè)名字可能就會(huì)望而卻步窜护，在面試的時(shí)候也非常害怕被問(wèn)到動(dòng)態(tài)規(guī)劃的題目效斑。實(shí)際上，它并不是不是一種確定的算法柱徙，它是一種最優(yōu)化的方法求解問(wèn)題的思想或方法缓屠。它是由美國(guó)數(shù)學(xué)家貝爾曼（Bellman）在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)提出。不過(guò)护侮，與之對(duì)應(yīng)的還有一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃敌完，如：線性規(guī)劃、非線性規(guī)劃等羊初。在運(yùn)籌學(xué)中滨溉，動(dòng)態(tài)規(guī)劃是的非常重要的內(nèi)容，在各個(gè)行業(yè)領(lǐng)域都有著廣泛的應(yīng)用长赞。我們?nèi)绾卫斫鈩?dòng)態(tài)規(guī)劃晦攒？

如果一個(gè)問(wèn)題的最優(yōu)解可以通過(guò)其子問(wèn)題的最優(yōu)解經(jīng)過(guò)推導(dǎo)得到，那么得哆，我們就可以先求出其子問(wèn)題的最優(yōu)解脯颜，根據(jù)子問(wèn)題的解得出原問(wèn)題的最優(yōu)解。如果子問(wèn)題有較多的重復(fù)出現(xiàn)贩据，為了減少重復(fù)計(jì)算伐脖，降低時(shí)間復(fù)雜度，則可以自底向上從最終子問(wèn)題向原問(wèn)題逐步求解并先將子問(wèn)題存儲(chǔ)起來(lái)乐设，在求解大的子問(wèn)題時(shí)可以直接從表中查詢子問(wèn)題的解，這就是動(dòng)態(tài)規(guī)劃的基本思想绎巨。

簡(jiǎn)單來(lái)來(lái)理解就是將一個(gè)大問(wèn)題簡(jiǎn)化成若干子問(wèn)題近尚，并存入一個(gè)表中，再根據(jù)數(shù)據(jù)表中子問(wèn)題的解求出大問(wèn)題的解场勤。這種算法看上去是不是很熟悉戈锻？其實(shí)，動(dòng)態(tài)規(guī)劃和分治算法類似和媳，我們也常常將其和分治算法進(jìn)行比較格遭。它們都需要將其分解成若干子問(wèn)題并求解子問(wèn)題。不同的是分治算法是自頂向下求解各子問(wèn)題留瞳，然后合并子問(wèn)題的解從而得到原問(wèn)題的解拒迅；而動(dòng)態(tài)規(guī)劃是將子問(wèn)題拆解之后，自底向上求解子問(wèn)題的解并將存儲(chǔ)結(jié)果存儲(chǔ)起來(lái)，在求解大的子問(wèn)題時(shí)直接查詢子問(wèn)題的解璧微，算法效率也將大大的提高作箍。

理論描述太過(guò)生硬和枯燥，我們直接來(lái)看一個(gè)例子前硫。

斐波那契數(shù)列

斐波那契數(shù)列

斐波那契數(shù)列是一個(gè)非常神奇的數(shù)列胞得，它由意大利數(shù)學(xué)家萊昂納-斐波那契提出，其特征是數(shù)列某一項(xiàng)的值是前兩項(xiàng)的和屹电，也可以稱作黃金分割數(shù)列阶剑。

萊昂納多·斐波那契

我們可以用下面的通項(xiàng)公式來(lái)表示斐波那契數(shù)列。

從斐波那契數(shù)列的公式中可知危号，數(shù)列的第n(n>2)項(xiàng)的值f(n)等于f(n)+f(n-1)牧愁，如果要求得f(n)值就需要先求得f(n-1)和f(n-2)的值，為了便于分析葱色，我們當(dāng)假設(shè)n=6递宅，我們可以按照下圖進(jìn)行分解，一步步分解成小的值苍狰。

斐波那契

看了上面的圖办龄，想必大家腦海中一種想到了程序的實(shí)現(xiàn)，我們可以直接通過(guò)遞歸的方法就可以求出n項(xiàng)的值淋昭，程序很容易俐填，如下所示。

int fib(int n)
{
    if(n==1 || n==2) return 1;
    return fib(n-1) + fib(n-2);
}

但是翔忽，很明顯這種算法是指數(shù)時(shí)間復(fù)雜度O(2^n)英融，其復(fù)雜度會(huì)隨著n的增加成指數(shù)增長(zhǎng)，當(dāng)n取到一定大時(shí)歇式，將需要很長(zhǎng)的時(shí)間驶悟，顯然這不是一種最優(yōu)的算法。不過(guò)材失，仔細(xì)觀察上圖的各個(gè)分解項(xiàng)痕鳍，我們會(huì)發(fā)現(xiàn)圖中有很多重復(fù)的子項(xiàng)，這就是上面這種遞歸算法復(fù)雜度較高的原因龙巨。那么笼呆，還能不能進(jìn)行優(yōu)化呢？答案是肯定的旨别。

我們可以通過(guò)動(dòng)態(tài)規(guī)劃的思想來(lái)優(yōu)化上面這個(gè)算法诗赌，為了避免大量的重復(fù)計(jì)算，我們可以從最底層的子問(wèn)題開始計(jì)算秸弛，并通過(guò)一個(gè)表來(lái)存儲(chǔ)這些子問(wèn)題的值铭若，當(dāng)再次遇到這個(gè)值就不需要再重新計(jì)算洪碳。

如下面的程序，我們從最小的子問(wèn)題n=1,2開始向上計(jì)算奥喻，并且定義了一個(gè)vector容器用來(lái)存儲(chǔ)被計(jì)算過(guò)的子問(wèn)題的值偶宫，下次再計(jì)算大問(wèn)題時(shí)直接調(diào)用容器里的值即可。

int fib(int n)
{
    vector<int> dp(n, 0);

    dp[0] = dp[1] = 1;
    for (int i = 2; i < n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n-1];
}

很明顯上面的這種算法环鲤，大大降低了算法的時(shí)間復(fù)雜度纯趋，現(xiàn)在的時(shí)間復(fù)雜度就是O(n)了。不過(guò)冷离，雖然時(shí)間復(fù)雜度降低了吵冒，這卻是犧牲了空間換取過(guò)來(lái)的。實(shí)際上我們還可以進(jìn)一步去優(yōu)化西剥，從公式上我們分析可以看出痹栖，要求出某一項(xiàng)的值我們需要先求出其前兩項(xiàng)子問(wèn)題的值，當(dāng)我們自下而上求解子問(wèn)題的過(guò)程中瞭空，我們直接保存連續(xù)兩項(xiàng)子問(wèn)題的值即可揪阿。

int fib(int n)
{
    int dp[2]={1,1};

    for (int i = 2; i < n; i++)
    {
        int tmp = dp[0];
        dp[0] = dp[1];
        dp[1] = dp[1] + tmp;
    }

    return dp[1];
}

最長(zhǎng)上升子序列

嚴(yán)格意義上來(lái)說(shuō)，上面的斐波那契數(shù)列也不完全算是動(dòng)態(tài)規(guī)劃問(wèn)題咆畏。因?yàn)閺膭?dòng)態(tài)規(guī)劃的定義上來(lái)看南捂，動(dòng)態(tài)規(guī)劃問(wèn)題一般滿足三個(gè)性質(zhì)：

• 最優(yōu)化原理：如果原問(wèn)題的最優(yōu)解所分解出的子問(wèn)題的解也是最優(yōu)的，我們就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)旧找，原問(wèn)題的最優(yōu)解可以有子問(wèn)題的最優(yōu)解推導(dǎo)得出溺健；
• 無(wú)后效性：某階段狀態(tài)一旦確定，這個(gè)狀態(tài)以后決策的影響钮蛛，它只與當(dāng)前狀態(tài)有關(guān)鞭缭；
• 有重疊子問(wèn)題：子問(wèn)題可能會(huì)在下一階段決策中被重復(fù)多次用到。

根據(jù)動(dòng)態(tài)規(guī)劃問(wèn)題的這三個(gè)性質(zhì)我們?cè)倏戳硗庖粋€(gè)例子魏颓，最長(zhǎng)上升子序列（Longest Increasing Subsequence）問(wèn)題岭辣，簡(jiǎn)稱LIS，這是一個(gè)非常經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題甸饱。

有一個(gè)長(zhǎng)度為n的數(shù)列a0, a1, ..., a(n-1)易结，求出這個(gè)序列中最長(zhǎng)的上升子序列的長(zhǎng)度。所謂上升子序列指的是對(duì)于任意的i<j都滿足a(i)<a(j)的子序列柜候。例如，一個(gè)序列為{6, 3, 5, 4, 7, 8, 1, 10}躏精，那么渣刷，它的最長(zhǎng)上升子序列為{3, 5, 7, 8, 10}或{3, 4, 7, 8, 10}。

我們先將原問(wèn)題進(jìn)行分解矗烛，依次拆解成子問(wèn)題辅柴，如下表：

子序列

我們的代碼可以按照下面來(lái)實(shí)現(xiàn)箩溃，其中，程序里我們用dp數(shù)組保存各個(gè)子序列以nums[i]結(jié)尾的最長(zhǎng)子序列長(zhǎng)度碌嘀，max存儲(chǔ)最長(zhǎng)子序列的長(zhǎng)度涣旨。

int maxLIS(std::vector<int>& nums)
{
    int max = 1;
    std::vector<int> dp(nums.size(), 1);

    for(int i = 1;i< nums.size(); i++)
    {
        for(int j=0; j<i; j++)
        {
            if(nums[i]>nums[j])
            {
                dp[i] = dp[j] + 1;
            }
            max = std::max(dp[i], max);
        }
    }

    return max;
}

通過(guò)上面的兩個(gè)例子，大家都學(xué)廢了嗎股冗？常見的還有很多問(wèn)題可以使用動(dòng)態(tài)規(guī)劃的方法解決霹陡，比如，背包問(wèn)題止状，硬幣找零烹棉，最短路徑等。動(dòng)態(tài)規(guī)劃不是一種固定的算法怯疤，對(duì)應(yīng)的問(wèn)題也是多種多樣浆洗，但大家只要掌握了其基本的思想，就可以輕松的解出相應(yīng)的問(wèn)題集峦，大家趕快去嘗試一下吧伏社！

本文首發(fā)公眾號(hào)：Will的大食堂，轉(zhuǎn)載請(qǐng)聯(lián)系微信：yuzaiduzhong塔淤。