hello大家好 我是大家的學習成長小伙伴Captain

動態(tài)規(guī)劃，大家肯定都聽過這個名詞，這個是很經典的一個解決問題的思路，也是很有技巧的，一般大廠也喜歡問這種類型的問題

今天我們一起來學習一下動態(tài)規(guī)劃到底是個什么

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

動態(tài)規(guī)劃（英語：Dynamic programming，簡稱DP）是一種在數(shù)學、管理科學、計算機科學、經濟學和生物信息學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。

?

動態(tài)規(guī)劃常常適用于有重疊子問題[1]和最優(yōu)子結構性質的問題，動態(tài)規(guī)劃方法所耗時間往往遠少于樸素解法。

?

動態(tài)規(guī)劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。

?

通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化（en:memoization）存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數(shù)目關于輸入的規(guī)模呈指數(shù)增長時特別有用。

核心思想

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

動態(tài)規(guī)劃算法的基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。

在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。

按照定義來看，動態(tài)規(guī)劃就是把一個大問題然后拆分成很多小問題，這個本身是沒啥問題的，其實啊，我個人覺得這不是動態(tài)規(guī)劃的核心思想

事實上是任何大問題都能拆解成許多小問題，一個大問題之所以能用動態(tài)規(guī)劃來解決，并不是因為它可以拆解成很多小問題，這不是關鍵

動態(tài)規(guī)劃的本質不在于是遞推或是遞歸，也不需要糾結是不是內存換時間，本質是解決的這些小問題是否能夠被重復調用，這就是問題是否可以用動態(tài)規(guī)劃解決的要素

我們先來看一個最熟悉的例子

斐波那契數(shù)列（Fibonacci polynomial）

計算斐波那契數(shù)列（Fibonacci polynomial）的一個最基礎的算法是，直接按照定義計算（函數(shù)遞歸）：

???function?fib(n）???????if?n?=?0?or?n?=?1???????????return?n       return fib(n ? 1) + fib（n ? 2）

當n=5時，fib(5)的計算過程如下:

?

fib(5)fib(4)?+?fib(3)(fib(3)?+?fib(2))?+?(fib(2)?+?fib(1))((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))(((fib(1)?+?fib(0))?+?fib(1))?+?(fib(1)?+?fib(0)))?+?((fib(1)?+?fib(0))?+?fib(1))

由上面可以看出，這種算法對于相似的子問題進行了重復的計算，因此不是一種高效的算法。實際上，該算法的運算時間是指數(shù)級增長的。

我們可以通過保存已經計算過的子問題的解來避免重復計算

? ? ? ? ?

再來看一個類似的例子，青蛙跳臺階

一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個 10 級的臺階總共有多少種跳法。

其實這個問題思路也是比較簡單的，要想跳到第10級臺階，要么是先跳到第9級，然后再跳1級臺階上去;要么是先跳到第8級，然后一次邁2級臺階上去。

同理，要想跳到第9級臺階，要么是先跳到第8級，然后再跳1級臺階上去;要么是先跳到第7級，然后一次邁2級臺階上去。

要想跳到第8級臺階，要么是先跳到第7級，然后再跳1級臺階上去;要么是先跳到第6級，然后一次邁2級臺階上去。

假設跳到第n級臺階的跳數(shù)我們定義為f(n)，可以得出公式：

f（10） = f（9）+f(8)f (9)  = f(8) + f(7)f (8)  = f(7) + f(6)...f(3) = f(2) + f(1)
即通用公式為: f(n) = f(n-1) + f(n-2)

那f(2) 或者 f(1) 等于多少呢？

?

當只有2級臺階時，有兩種跳法，第一種是直接跳兩級，第二種是先跳一級，然后再跳一級。即f(2) = 2;

當只有1級臺階時，只有一種跳法，即f（1）= 1；

public int getNum(int n) {??if(n?==?1){??????return?1;???}???if(n?==?2){??????return?2;???}??return?getNum(n-1)?+?getNum(n-2);}

大家通過看上面兩個例子心中是怎么想的呢

聰明的你們應該早已經發(fā)現(xiàn)其中的相似點了，沒錯，它們的共同點就是都是有一些子問題作為根基，然后這些子問題會被重復的調用，計算

要計算最大的值，就必須先計算子問題，要計算子問題，就必須計算更子的問題

仔細想一下這個計算過程，太多太多的重復計算了，每一個都被計算了不止一次，尤其是f(1)這種，所以這種是很低效的

既然存在了大量的重復計算，我們就可以先把計算好的答案保存下來，其實也就是一個備忘錄，等到下次需要的話，也就是先去備忘錄查詢一下，如果有，就直接取備忘錄的值就可以了，備忘錄沒有才開始計算

類似于我們平時系統(tǒng)中的緩存的效果

?

動態(tài)規(guī)劃跟帶備忘錄的遞歸解法基本思想是一致的，都是減少重復計算，時間復雜度也都是差不多。

但是呢

?

帶備忘錄的遞歸，是從f(10)往f(1）方向延伸求解的，所以也稱為自頂向下的解法。

動態(tài)規(guī)劃從較小問題的解，由交疊性質，逐步決策出較大問題的解，它是從f(1)往f(10）方向，往上推求解，所以稱為自底向上的解法。

動態(tài)規(guī)劃有幾個典型特征，最優(yōu)子結構、狀態(tài)轉移方程、邊界、重疊子問題。

在青蛙跳階問題中：

?

f(n-1)和f(n-2) 稱為 f(n) 的最優(yōu)子結構

f(n)= f（n-1）+f（n-2）就稱為狀態(tài)轉移方程

f(1) = 1, f(2) = 2 就是邊界啦

比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重疊子問題。

動態(tài)規(guī)劃中的解題套路

通過上面說了這么多了，我們知道動態(tài)規(guī)劃的關鍵在于：存在重疊子問題！

動態(tài)規(guī)劃的本質不在于是遞推或是遞歸，也不需要糾結是不是內存換時間，本質是解決的這些小問題是否能夠被重復調用，這就是問題是否可以用動態(tài)規(guī)劃解決的要素

• 將原問題分解為子問題
• 確定狀態(tài)
• 確定一些初始狀態(tài)（邊界狀態(tài)）的值
  
• 寫出狀態(tài)轉移方程

如果一個大問題，可以把所有可能的答案都窮舉出來，窮舉出來之后會發(fā)現(xiàn)有很多重疊的子問題，就可以考慮使用動態(tài)規(guī)劃

比如一些求最值的場景，如最長遞增子序列、最小編輯距離、背包問題、湊零錢問題等等，都是動態(tài)規(guī)劃的經典應用場景。

?

動態(tài)規(guī)劃的核心思想就是拆分子問題，記住過往，減少重復計算。并且動態(tài)規(guī)劃一般都是自底向上的，因此到這里，基于青蛙跳階問題，我總結了一下我做動態(tài)規(guī)劃的思路：

1、將原問題分解為子問題

把原問題分解為若干個子問題，子問題和原問題形式相同 或類似，只不過規(guī)模變小了。

子問題都解決，原問題即解 決(數(shù)字三角形例）。l 子問題的解一旦求出就會被保存，所以每個子問題只需求 解一次。?

?

2、確定狀態(tài)

在用動態(tài)規(guī)劃解題時，我們往往將和子問題相 關的各個變量的一組取值，稱之為一個“狀態(tài)”。

一個“狀態(tài)”對應于一個或多個子問題， 所謂某個“狀態(tài)”下的“值”，就是這個“狀 態(tài)”所對應的子問題的解。

所有“狀態(tài)”的集合，構成問題的“狀態(tài)空間”?！盃顟B(tài) 空間”的大小，與用動態(tài)規(guī)劃解決問題的時間復雜度直接相關。在數(shù)字三角形的例子里，一共有N×(N+1)/2個數(shù)字，所以這個 問題的狀態(tài)空間里一共就有N×(N+1)/2個狀態(tài)。

整個問題的時間復雜度是狀態(tài)數(shù)目乘以計算每個狀態(tài)所需時間。? ? ? ? ? ??

在數(shù)字三角形里每個“狀態(tài)”只需要經過一次，且在每個 狀態(tài)上作計算所花的時間都是和N無關的常數(shù)。??

?

用動態(tài)規(guī)劃解題，經常碰到的情況是，K個整型變量能 構成一個狀態(tài)（如數(shù)字三角形中的行號和列號這兩個變量 構成“狀態(tài)”）。如果這K個整型變量的取值范圍分別是 N1, N2, ……Nk，那么，我們就可以用一個K維的數(shù)組 array[N1] [N2]……[Nk]來存儲各個狀態(tài)的“值”。

這個 “值”未必就是一個整數(shù)或浮點數(shù)，可能是需要一個結構 才能表示的，那么array就可以是一個結構數(shù)組。一個 “狀態(tài)”下的“值”通常會是一個或多個子問題的解。

?

3、確定一些初始狀態(tài)（邊界狀態(tài)）的值

???????

以“數(shù)字三角形”為例，初始狀態(tài)就是底邊數(shù)字，值 就是底邊數(shù)字值。

4、確定狀態(tài)轉移方程

定義出什么是“狀態(tài)”，以及在該 “狀態(tài)”下的“值”后，就要 找出不同的狀態(tài)之間如何遷移――即如何從一個或多個“值”已知的 “狀態(tài)”，求出另一個“狀態(tài)”的“值”(“人人為我”遞推型)。

狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作“狀態(tài)轉移方程”。

?

能用動規(guī)解決的問題的特點

1) 問題具有最優(yōu)子結構性質。

如果問題的最優(yōu)解所包含的 子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結 構性質。

?

2) 無后效性。

當前的若干個狀態(tài)值一旦確定，則此后過程 的演變就只和這若干個狀態(tài)的值有關，和之前是采取哪 種手段或經過哪條路徑演變到當前的這若干個狀態(tài)，沒有關系。