對於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”

就不翻譯了，相信大家都能看懂。

現在，我們來看一下動態規劃的 官方定義 ：

動態規劃算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。

動態規劃算法的基本思想與分治法類似，也是將待求解的問題分解爲若干個子問題（階段），按順序求解子階段，前一子問題的解，爲後一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。

按照定義， 動態規劃的原理是將一個問題分解成子問題，逐漸求解局部最優解並擴展，最終得出全局最優解 。但是我覺得的這個不是動態規劃的核心思想，或者說，一個”大問題“之所以能用”動態規劃解決，並不是因爲它能拆解成一堆小問題， 而是這些”小問題“會不會被被重複調用。 

這個概念很重要，實際上很多問題都可以拆解成小問題來解決，例如我們之前講的貪心算法，但這個區別決定了該選取哪種算法 。

二、動態規劃能解決什麼問題？

如果一個問題滿足以下兩點，那麼它就能用動態規劃解決。

（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協議