尋夢新聞LINE@每日推播熱門推薦文章，趣聞不漏接❤️
對於AI產品經理來說，掌握一些算法是必要的。本文從是什麼、解決什麼問題、應用場景、應用過程和相幹案例等幾個方面，講述了AI產品經理必修的動態規划算法，希望對你有幫助。
對於AI產品經理來說，掌握一些算法是必要的。本文從是什麼、解決什麼問題、應用場景、應用過程和相幹案例等幾個方面，講述了AI產品經理必修的動態規划算法，希望對你有幫助。
喬治·桑塔亞納說過，「那些遺忘過去的人註定要重蹈覆轍。」這句話放在問題求解過程中也同樣適用。不懂動態規劃的人會在解決過的問題上再次浪費時間，懂的人則會事半功倍。要了解這句話，得從動態規劃的含義說起。
一、什麼是動態規劃？
quora上有這樣一個問題:
How should I explain dynamic programming to a 4-year old?底下有個42K讚同的答案，是這樣說的:
*writes down 「1+1+1+1+1+1+1+1 =」 on a sheet of paper*」What’s that equal to?」
*counting* 「Eight!」
*writes down another 「1+」 on the left*
「What about that?」
*quickly* 「Nine!」
「How’d you know it was nine so fast?」」You just added one more」
「So you didn’t need to recount because you remembered there were eight!DynamicProgramming is just a fancy way to say ‘remembering stuff to save time later」
How should I explain dynamic programming to a 4-year old?底下有個42K讚同的答案，是這樣說的:
*writes down 「1+1+1+1+1+1+1+1 =」 on a sheet of paper*」What’s that equal to?」
*counting* 「Eight!」
*writes down another 「1+」 on the left*
「What about that?」
*quickly* 「Nine!」
「How’d you know it was nine so fast?」」You just added one more」
「So you didn’t need to recount because you remembered there were eight!DynamicProgramming is just a fancy way to say ‘remembering stuff to save time later」
就不翻譯了，相信大家都能看懂。
現在，我們來看一下動態規劃的官方定義：
動態規划算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞回（或者說分治）的方式去解決。
動態規划算法的基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。
按照定義，動態規劃的原理是將一個問題分解成子問題，逐漸求解局部最優解並擴展，最終得出全局最優解。但是我覺得的這個不是動態規劃的核心思想，或者說，一個」大問題「之所以能用」動態規劃解決，並不是因為它能拆解成一堆小問題，而是這些」小問題「會不會被被重復調用。
這個概念很重要，實際上很多問題都可以拆解成小問題來解決，例如我們之前講的貪心算法，但這個區別決定了該選取哪種算法 。
二、動態規劃能解決什麼問題？
如果一個問題滿足以下兩點，那麼它就能用動態規劃解決。
（1）問題的答案依賴於問題的規模，也就是問題的所有答案構成了一個數列。舉個簡單的例子，1人有2條腿，2個人有4條腿，n個人有多少條腿?答案是2n條腿。這裡的2n是問題的答案，n則是問題的規模，顯然問題的答案是依賴於問題的規模的答案是因變量，問題規模是自變量。因此，問題在所有規模下的答案可以構成一個數列(f(1)，f(2)…f(n))，比如剛剛「數腿」的例子就構成了間隔為2的等差數列(0,2.4….2n) 。
（2）大規模問題的答案可以由小規模問題的答案遞回得到，還是剛剛「數腿」 的例子，顯然f(n)可以甚於f(n-1) 求得: f(n)= f(n-1)+2
三、動態規劃的應用？
應用場景：動態規劃比較合適的就是來求最優問題的，比如求最大值，最小值等等。它可以顯著的降低龐雜度，節約計算時間。所有的導航系統都採用了動態規劃。
我們就是以導航為例來看看動態規劃吧。
比如，我們想找到從北京到廣州的最短行車路線或者最快行車路線。當然，最直接的笨辦法是把所有可能的路線看一遍，然後找到最優的。
這種辦法只有在節點數是個位數的圖中還行得通，當圖的節點數（城市數目）有幾十個的時候，計算的龐雜度就已經讓人甚至計算機難以接受了，因為所有可能路徑的個數隨著節點數的增長而成呈指數增長（或者說幾何級數），也就是說每增加一個城市，龐雜度要大一倍，顯然我們的導航系統中不會用這種笨辦法。
以上面的問題為例，當我們要找從北京到廣州的最短路線時，我們先不妨倒過來想這個問題：假如我們找到了所要的最短路線（稱為路線一），如果它經過鄭州，那麼從北京到鄭州的這條子路線（比如是北京-> 保定->石家莊->鄭州，稱為子路線一），必然也是所有從北京到鄭州的路線中最短的。
在實際實現算法時，我們又正過來解決這個問題，也就是說，要想找到從北京到廣州的最短路線，先要找到從北京到鄭州的最短路線。當然，聰明的讀者可能已經發現其中的一個」漏洞」，就是我們在還沒有找到全程最短路線前，不能肯定它一定經過鄭州。不過沒有關係，只要我們在圖上橫切一刀，這一 刀要保證將任何從北京到廣州的路一截二，如下圖：
那麼從廣州到北京的最短路徑必須經過這一條線上的某個城市（圖中藍色的菱形） 。我們可以先找到從北京出發到這條線上所有城市的最短路徑，最後得到的全程最短路線一定包括這些局部最短路線中的一條，這樣，我們就可以將一個」尋找全程最短路線」的問題，分解成一個個小的尋找局部最短路線的問題。
只要我們將這條橫切線從北京向廣州推移，直到廣州為止，我們的全程最短路線就找到了。這便是動態規劃的原理。採用動態規劃可以大大降低最短路徑的計算龐雜度。
四、動態規劃的過程？
當要應用動態規劃來解決問題時，歸根結底就是將動態規劃拆分成以下三個關鍵目標。
1. 建立狀態轉移方程
這一步是最難的，大部分人都被卡在這裡。這步沒太多的規律可說，只需抓住個思維: 當做已經知道f(1)~ f(n- 1)的值，然後想辦法利用它們求得f(n)。
2. 緩存並復用以往結果
這一步不難，但是很重要。如果沒有合適地處理，很有可能就是指數和線性時間龐雜度的區別。在我們上面的例子中，每加入一條橫截線，線上平均有十個城市，從廣州到北京最多經過十五個城市，那麼採用動態規劃的計算量是 10×10×15，而採用窮舉路徑的笨辦法是 10 的 15 次方，前後差了萬億倍。
3. 按順序從小往大算
這裡的「小和「大」對應的是問題的規模，在這裡也就是我們要從f(0), f(1).到f(n)依次順序計算。這點從導航的例子來看，似乎顯而易見，因為狀態方程基本限制了你只能從小到大一步步遞回出最終的結果。
五、經典動態規劃
我們來嘗試用動態規劃實現經典斐波那契數列
斐波那契數列: 0,1. 1,2,3,5,8, 13, 21,34.55, 89, 1443….
它遵循這樣的規律:當前值為前兩個值的和。
那麼第n個值為多少?
我們用兩種方法來做比較:
方法一：簡單遞歸
如上所示，代碼簡單易懂，然而這代碼卻極其低效。
下圖通過展示求解f(6)的過程說明了其原因。如圖，隨著遞歸的深入，計算任務不斷地翻倍！
方法二：動態規劃
先上代碼。看不懂也沒關係，看看如果完成這三個目標的就行了。
目標1，建立狀態轉移方程(完成)。也就是前面的f(n)= f(n-1)+ f(n- 2)。
目標2，緩存並復用以往結果(完成)。在線性規劃解法中，我們把結果緩存在results列表，同時在results[il = rsutsti11 + resultsti 2]中進行了復用。這相當於我們只需完成圖2中紅色部分的計算任務即可，時間龐雜度瞬間降為O(n) 。
目標3,按順序從小往大算(完成)。 for循環實現了從0到n的順序求解，讓問題按著從小規模往大規模求解的順序走。
堪稱完美！
本文由 @CARRIE 原創發布於人人都是產品經理。未經許可，禁止轉載
題圖來自Unsplash，基於CC0協議