對于AI產(chǎn)品經(jīng)理來說，掌握一些算法是必要的。本文從是什么、解決什么問題、應(yīng)用場景、應(yīng)用過程和相關(guān)案例等幾個方面，講述了AI產(chǎn)品經(jīng)理必修的動態(tài)規(guī)劃算法，希望對你有幫助。

喬治·桑塔亞納說過，“那些遺忘過去的人注定要重蹈覆轍?！边@句話放在問題求解過程中也同樣適用。不懂動態(tài)規(guī)劃的人會在解決過的問題上再次浪費時間，懂的人則會事半功倍。要了解這句話，得從動態(tài)規(guī)劃的含義說起。

一、什么是動態(tài)規(guī)劃？

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”

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

現(xiàn)在，我們來看一下動態(tài)規(guī)劃的官方定義：

動態(tài)規(guī)劃算法是通過拆分問題，定義問題狀態(tài)和狀態(tài)之間的關(guān)系，使得問題能夠以遞推（或者說分治）的方式去解決。

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

按照定義，動態(tài)規(guī)劃的原理是將一個問題分解成子問題，逐漸求解局部最優(yōu)解并擴展，最終得出全局最優(yōu)解。但是我覺得的這個不是動態(tài)規(guī)劃的核心思想，或者說，一個”大問題“之所以能用”動態(tài)規(guī)劃解決，并不是因為它能拆解成一堆小問題，而是這些”小問題“會不會被被重復調(diào)用。?

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

二、動態(tài)規(guī)劃能解決什么問題？

如果一個問題滿足以下兩點，那么它就能用動態(tài)規(guī)劃解決。

（1）問題的答案依賴于問題的規(guī)模，也就是問題的所有答案構(gòu)成了一個數(shù)列。舉個簡單的例子，1人有2條腿，2個人有4條腿，n個人有多少條腿?答案是2n條腿。這里的2n是問題的答案，n則是問題的規(guī)模，顯然問題的答案是依賴于問題的規(guī)模的答案是因變量，問題規(guī)模是自變量。因此，問題在所有規(guī)模下的答案可以構(gòu)成一個數(shù)列(f(1)，f(2)…f(n))，比如剛剛“數(shù)腿”的例子就構(gòu)成了間隔為2的等差數(shù)列(0,2.4….2n) 。

（2）大規(guī)模問題的答案可以由小規(guī)模問題的答案遞推得到，還是剛剛“數(shù)腿” 的例子，顯然f(n)可以甚于f(n-1) 求得: f(n)= f(n-1)+2

三、動態(tài)規(guī)劃的應(yīng)用？

應(yīng)用場景：動態(tài)規(guī)劃比較合適的就是來求最優(yōu)問題的，比如求最大值，最小值等等。它可以顯著的降低復雜度，節(jié)約計算時間。所有的導航系統(tǒng)都采用了動態(tài)規(guī)劃。

我們就是以導航為例來看看動態(tài)規(guī)劃吧。

比如，我們想找到從北京到廣州的最短行車路線或者最快行車路線。當然，最直接的笨辦法是把所有可能的路線看一遍，然后找到最優(yōu)的。

這種辦法只有在節(jié)點數(shù)是個位數(shù)的圖中還行得通，當圖的節(jié)點數(shù)（城市數(shù)目）有幾十個的時候，計算的復雜度就已經(jīng)讓人甚至計算機難以接受了，因為所有可能路徑的個數(shù)隨著節(jié)點數(shù)的增長而成呈指數(shù)增長（或者說幾何級數(shù)），也就是說每增加一個城市，復雜度要大一倍，顯然我們的導航系統(tǒng)中不會用這種笨辦法。

以上面的問題為例，當我們要找從北京到廣州的最短路線時，我們先不妨倒過來想這個問題：假如我們找到了所要的最短路線（稱為路線一），如果它經(jīng)過鄭州，那么從北京到鄭州的這條子路線（比如是北京-> 保定->石家莊->鄭州，稱為子路線一），必然也是所有從北京到鄭州的路線中最短的。

在實際實現(xiàn)算法時，我們又正過來解決這個問題，也就是說，要想找到從北京到廣州的最短路線，先要找到從北京到鄭州的最短路線。當然，聰明的讀者可能已經(jīng)發(fā)現(xiàn)其中的一個”漏洞”，就是我們在還沒有找到全程最短路線前，不能肯定它一定經(jīng)過鄭州。不過沒有關(guān)系，只要我們在圖上橫切一刀，這一 刀要保證將任何從北京到廣州的路一截二，如下圖：

那么從廣州到北京的最短路徑必須經(jīng)過這一條線上的某個城市（圖中藍色的菱形） 。我們可以先找到從北京出發(fā)到這條線上所有城市的最短路徑，最后得到的全程最短路線一定包括這些局部最短路線中的一條，這樣，我們就可以將一個”尋找全程最短路線”的問題，分解成一個個小的尋找局部最短路線的問題。

只要我們將這條橫切線從北京向廣州推移，直到廣州為止，我們的全程最短路線就找到了。這便是動態(tài)規(guī)劃的原理。采用動態(tài)規(guī)劃可以大大降低最短路徑的計算復雜度。

四、動態(tài)規(guī)劃的過程？

當要應(yīng)用動態(tài)規(guī)劃來解決問題時，歸根結(jié)底就是將動態(tài)規(guī)劃拆分成以下三個關(guān)鍵目標。

1. 建立狀態(tài)轉(zhuǎn)移方程

這一步是最難的，大部分人都被卡在這里。這步?jīng)]太多的規(guī)律可說，只需抓住個思維: 當做已經(jīng)知道f(1)~ f(n- 1)的值，然后想辦法利用它們求得f(n)。

2. 緩存并復用以往結(jié)果

這一步不難，但是很重要。如果沒有合適地處理，很有可能就是指數(shù)和線性時間復雜度的區(qū)別。在我們上面的例子中，每加入一條橫截線，線上平均有十個城市，從廣州到北京最多經(jīng)過十五個城市，那么采用動態(tài)規(guī)劃的計算量是 10×10×15，而采用窮舉路徑的笨辦法是 10 的 15 次方，前后差了萬億倍。

3. 按順序從小往大算

這里的“小和“大”對應(yīng)的是問題的規(guī)模，在這里也就是我們要從f(0), f(1).到f(n)依次順序計算。這點從導航的例子來看，似乎顯而易見，因為狀態(tài)方程基本限制了你只能從小到大一步步遞推出最終的結(jié)果。

五、經(jīng)典動態(tài)規(guī)劃

我們來嘗試用動態(tài)規(guī)劃實現(xiàn)經(jīng)典斐波那契數(shù)列

斐波那契數(shù)列: 0,1. 1,2,3,5,8, 13, 21,34.55, 89, 1443….

它遵循這樣的規(guī)律:當前值為前兩個值的和。

那么第n個值為多少?

我們用兩種方法來做比較:

方法一：簡單遞歸

如上所示，代碼簡單易懂，然而這代碼卻極其低效。

下圖通過展示求解f(6)的過程說明了其原因。如圖，隨著遞歸的深入，計算任務(wù)不斷地翻倍！

方法二：動態(tài)規(guī)劃

先上代碼?？床欢矝]關(guān)系，看看如果完成這三個目標的就行了。

目標1，建立狀態(tài)轉(zhuǎn)移方程(完成)。也就是前面的f(n)= f(n-1)+ f(n- 2)。

目標2，緩存并復用以往結(jié)果(完成)。在線性規(guī)劃解法中，我們把結(jié)果緩存在results列表，同時在results[il = rsutsti11 + resultsti 2]中進行了復用。這相當于我們只需完成圖2中紅色部分的計算任務(wù)即可，時間復雜度瞬間降為O(n) 。

目標3,按順序從小往大算(完成)。?for循環(huán)實現(xiàn)了從0到n的順序求解，讓問題按著從小規(guī)模往大規(guī)模求解的順序走。

堪稱完美！

本文由 @CARRIE 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來自Unsplash，基于CC0協(xié)議