動(dòng)態(tài)規(guī)劃是算法中比較常用的，題型很多，但中心思想實(shí)際上類(lèi)似于數(shù)學(xué)歸納，以遞推公式的方法計(jì)算結(jié)果，主要步驟就是求得遞推關(guān)系和初始值

動(dòng)態(tài)規(guī)劃，無(wú)非就是利用歷史記錄，來(lái)避免我們的重復(fù)計(jì)算。而這些歷史記錄，我們得需要一些變量來(lái)保存，一般是用一維數(shù)組或者二維數(shù)組來(lái)保存。下面我們先來(lái)講下做動(dòng)態(tài)規(guī)劃題很重要的三個(gè)步驟，

如果你聽(tīng)不懂，也沒(méi)關(guān)系，下面會(huì)有很多例題講解，估計(jì)你就懂了。之所以不配合例題來(lái)講這些步驟，也是為了怕你們腦袋亂了

第一步驟：定義數(shù)組元素的含義，上面說(shuō)了，我們會(huì)用一個(gè)數(shù)組，來(lái)保存歷史數(shù)組，假設(shè)用一維數(shù)組 dp[] 吧。這個(gè)時(shí)候有一個(gè)非常非常重要的點(diǎn)，就是規(guī)定你這個(gè)數(shù)組元素的含義，例如你的 dp[i] 是代表什么意思？

第二步驟：找出數(shù)組元素之間的關(guān)系式，我覺(jué)得動(dòng)態(tài)規(guī)劃，還是有一點(diǎn)類(lèi)似于我們高中學(xué)習(xí)時(shí)的歸納法的，當(dāng)我們要計(jì)算 dp[n] 時(shí)，是可以利用 dp[n-1]，dp[n-2].....dp[1]，來(lái)推出 dp[n] 的，也就是可以利用歷史數(shù)據(jù)來(lái)推出新的元素值，所以我們要找出數(shù)組元素之間的關(guān)系式，例如 dp[n] = dp[n-1] + dp[n-2]，這個(gè)就是他們的關(guān)系式了。而這一步，也是最難的一步，后面我會(huì)講幾種類(lèi)型的題來(lái)說(shuō)。

學(xué)過(guò)動(dòng)態(tài)規(guī)劃的可能都經(jīng)常聽(tīng)到最優(yōu)子結(jié)構(gòu)，把大的問(wèn)題拆分成小的問(wèn)題，說(shuō)時(shí)候，最開(kāi)始的時(shí)候，我是對(duì)最優(yōu)子結(jié)構(gòu)一夢(mèng)懵逼的。估計(jì)你們也聽(tīng)多了，所以這一次，我將換一種形式來(lái)講，不再是各種子問(wèn)題，各種最優(yōu)子結(jié)構(gòu)。所以大佬可別噴我再亂講，因?yàn)槲艺f(shuō)了，這是我自己平時(shí)做題的套路。

第三步驟：找出初始值。學(xué)過(guò)數(shù)學(xué)歸納法的都知道，雖然我們知道了數(shù)組元素之間的關(guān)系式，例如 dp[n] = dp[n-1] + dp[n-2]，我們可以通過(guò) dp[n-1] 和 dp[n-2] 來(lái)計(jì)算 dp[n]，但是，我們得知道初始值啊，例如一直推下去的話(huà)，會(huì)由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我們必須要能夠直接獲得 dp[2] 和 dp[1] 的值，而這，就是所謂的初始值。

由了初始值，并且有了數(shù)組元素之間的關(guān)系式，那么我們就可以得到 dp[n] 的值了，而 dp[n] 的含義是由你來(lái)定義的，你想求什么，就定義它是什么，這樣，這道題也就解出來(lái)了。

告別動(dòng)態(tài)規(guī)劃，連刷 40 道題，我總結(jié)了這些套路，看不懂你打我（萬(wàn)字長(zhǎng)文） - 知乎 (zhihu.com)