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

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

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

這里咱們只講它的核心思想，就兩點：

一、進階版遞歸

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

這個思想和遞歸是有點相似的，某種意義上我們可以認為動態(tài)規(guī)劃是對遞歸的一種優(yōu)化，是一種進階版的遞歸。

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

那么動態(tài)規(guī)劃和遞歸之間有何不同呢？主要體現(xiàn)在以下第二點——我們在解決n個子問題的時候，要留意在整體上有沒有做無用功。

二、備忘錄

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

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

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

那這兩個思想是不需要死記硬背呢？其實完全不需要。

咱們做程序員有一點很爽的就是，在你還不是管理者不是老板的時候，你的思路就變得很像是一個老板，因為程序員需要復(fù)用，需要管理子模塊，也需要解決復(fù)雜系統(tǒng)問題。

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

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

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

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

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

0x2寫在最后

簡單總結(jié)一下：

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

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

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