如何掌握動(dòng)態(tài)規(guī)劃算法的套路？

動(dòng)態(tài)規(guī)劃（Dynamic Programming），簡(jiǎn)稱(chēng)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í)可以直接從表中查詢(xún)子問(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ī)劃和分治算法類(lèi)似，我們也常常將其和分治算法進(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í)直接查詢(xún)子問(wèn)題的解，算法效率也將大大的提高。

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

斐波那契數(shù)列

斐波那契數(shù)列是一個(gè)非常神奇的數(shù)列，它由意大利數(shù)學(xué)家萊昂納-斐波那契提出，其特征是數(shù)列某一項(xiàng)的值是前兩項(xiàng)的和，也可以稱(chē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)題開(kāi)始計(jì)算，并通過(guò)一個(gè)表來(lái)存儲(chǔ)這些子問(wèn)題的值，當(dāng)再次遇到這個(gè)值就不需要再重新計(jì)算。

如下面的程序，我們從最小的子問(wèn)題n=1,2開(kāi)始向上計(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)的，我們就稱(chēng)該問(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)稱(chēng)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é)廢了嗎？常見(jiàn)的還有很多問(wèn)題可以使用動(dòng)態(tài)規(guī)劃的方法解決，比如，背包問(wèn)題，硬幣找零，最短路徑等。動(dòng)態(tài)規(guī)劃不是一種固定的算法，對(duì)應(yīng)的問(wèn)題也是多種多樣，但大家只要掌握了其基本的思想，就可以輕松的解出相應(yīng)的問(wèn)題，大家趕快去嘗試一下吧！