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

0x1動態規劃的核心思想

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

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

一、進階版遞歸

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

這個思想和遞歸是有點相似的，某種意義上我們可以認為動態規劃是對遞歸的一種優化，是一種進階版的遞歸。

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

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

二、備忘錄

通過備忘錄的方式保存中間狀態，使得不反復去計算已經求得的中間解，也就是說不浪費算力，不做無用功。

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

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

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

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

實際上，作為一個公司的老板，面對很多復雜的問題，用的基本思想就是動態規劃思想。

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

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

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

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

0x2寫在最后

簡單總結一下：

動態規劃的實質是分治思想和解決冗余，因此動態規劃是一種將問題實例分析為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優化問題的算法策略。

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

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