很多人會(huì)覺得算法很難，甚至?xí)X得考算法就是面試官在秀優(yōu)越、秀智商，其實(shí)每種算法的核心思想都很簡(jiǎn)單，都是可以用一句話或者兩三句話說清楚的，只要咱們把握了核心思想，那么完全不用死記硬背。

0x1動(dòng)態(tài)規(guī)劃的核心思想

咱們這里就不展開講動(dòng)態(tài)規(guī)劃的種種具體問題了，比如說斐波那契數(shù)列、背包問題、最小路徑問題等等，網(wǎng)上有很多，最終想要徹底掌握，肯定還需要自己去研究去實(shí)踐，并且用代碼去刷它個(gè)十道八道題的。

這里咱們只講它的核心思想，就兩點(diǎn)：

一、進(jìn)階版遞歸

任何看似很復(fù)雜很難解決的問題，其實(shí)都可以歸結(jié)為一系列子問題，無論一個(gè)問題有多復(fù)雜，只要它有解決方案，那么它就可以歸結(jié)為n個(gè)子問題。

這個(gè)思想和遞歸是有點(diǎn)相似的，某種意義上我們可以認(rèn)為動(dòng)態(tài)規(guī)劃是對(duì)遞歸的一種優(yōu)化，是一種進(jìn)階版的遞歸。

換一種說法就是分治法——將一個(gè)規(guī)模為n的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同，遞歸地解決這些問題，然后將各個(gè)子問題的解合并得到原問題的解。

那么動(dòng)態(tài)規(guī)劃和遞歸之間有何不同呢？主要體現(xiàn)在以下第二點(diǎn)——我們?cè)诮鉀Qn個(gè)子問題的時(shí)候，要留意在整體上有沒有做無用功。

二、備忘錄

通過備忘錄的方式保存中間狀態(tài)，使得不反復(fù)去計(jì)算已經(jīng)求得的中間解，也就是說不浪費(fèi)算力，不做無用功。

換一種說法就是貪心法——當(dāng)前的選擇可能要依賴于已經(jīng)做出的選擇，但不依賴于有待于做出的選擇和子問題，因此貪心法是自頂向下，一步一步地做出貪心的選擇。

帶著這兩個(gè)核心思想，相信你再去看動(dòng)態(tài)規(guī)劃的任何問題，都會(huì)感到非常輕松。

那這兩個(gè)思想是不需要死記硬背呢？其實(shí)完全不需要。

咱們做程序員有一點(diǎn)很爽的就是，在你還不是管理者不是老板的時(shí)候，你的思路就變得很像是一個(gè)老板，因?yàn)槌绦騿T需要復(fù)用，需要管理子模塊，也需要解決復(fù)雜系統(tǒng)問題。

實(shí)際上，作為一個(gè)公司的老板，面對(duì)很多復(fù)雜的問題，用的基本思想就是動(dòng)態(tài)規(guī)劃思想。

比如說你要達(dá)成某個(gè)業(yè)績(jī)目標(biāo)，那么你就會(huì)把它歸結(jié)為幾個(gè)子任務(wù)，并且把這幾個(gè)預(yù)期可以完成的子任務(wù)有機(jī)地組合在一起，比如說市場(chǎng)部、產(chǎn)品部、運(yùn)營部應(yīng)該怎么怎么做，最后你應(yīng)該如何把他們組合在一起，至于部門內(nèi)部要怎么實(shí)現(xiàn)，那完全是部門經(jīng)理進(jìn)一步遞歸下去做的事情，而且部門經(jīng)理用的方法，也可以稱之為算法吧，跟老板的思維是一模一樣的。這就是動(dòng)態(tài)規(guī)劃的第一個(gè)基本思想。

那么老板同樣也會(huì)用到動(dòng)態(tài)規(guī)劃的第二個(gè)基本思想，比如說，老板他需要觀察他的公司有沒有重復(fù)勞動(dòng)，有沒有在做無用功。

假設(shè)公司有五個(gè)項(xiàng)目組，他們的技術(shù)人員各自都做了一套同樣的功能，或者相似的功能，這里面其實(shí)就存在著重復(fù)造輪子的問題，產(chǎn)生了“算力”上的浪費(fèi)。

那么如果你是老板你該如何優(yōu)化呢？是不是可以抽出叫做一個(gè)技術(shù)中臺(tái)的部門呢，由這個(gè)部門來對(duì)所有項(xiàng)目組都需要用到的輪子，提供一個(gè)標(biāo)準(zhǔn)的、模板化的解決方案。這就是動(dòng)態(tài)規(guī)劃的第二個(gè)基本思想。

0x2寫在最后

簡(jiǎn)單總結(jié)一下：

動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分析為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。

動(dòng)態(tài)規(guī)劃所針對(duì)的問題有一個(gè)顯著的特征，即它對(duì)應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)，而動(dòng)態(tài)規(guī)劃的關(guān)鍵在于，對(duì)于重復(fù)的子問題，只在第一次遇到時(shí)求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不必要重新求解。

我們學(xué)習(xí)算法不止是學(xué)習(xí)算法本身，而是要善于總結(jié)算法的“道”——也就是背后的核心思想，思想一般都很簡(jiǎn)單，一旦你領(lǐng)悟了這個(gè)思想，同時(shí)能夠舉一反三，那么你以后就可以用這些思想解決更復(fù)雜、更實(shí)用的問題，甚至是管理公司。