因?yàn)榍耙欢谓恿藗€(gè)項(xiàng)目，所以呢，其實(shí)在前一段時(shí)間我就有寫過(guò)關(guān)于動(dòng)態(tài)規(guī)劃的一篇文章——淺談一下這個(gè)所謂的特殊算法——?jiǎng)討B(tài)規(guī)劃！鏈接如下：

https://blog.csdn.net/qq_41946557/article/details/104704964

但是在項(xiàng)目的講述中，如果我要使用到它，我怎么講述？忽的這樣一想，好像對(duì)其算法好像并沒(méi)有自己想的那個(gè)隨意。所以再來(lái)說(shuō)到說(shuō)到這個(gè)動(dòng)態(tài)規(guī)劃！

我們?cè)谝恍┧阉饕嫔纤阉鳌趧?dòng)態(tài)規(guī)劃時(shí)，你會(huì)發(fā)現(xiàn)關(guān)于使用動(dòng)態(tài)規(guī)劃的領(lǐng)域，可謂是各行各業(yè)。比如：基于動(dòng)態(tài)規(guī)劃的資源分配問(wèn)題，基于動(dòng)態(tài)規(guī)劃的路徑規(guī)劃方法等等等。其實(shí)早在最初的淺談動(dòng)態(tài)規(guī)劃中，我就提出過(guò)DP實(shí)際意義上說(shuō)是一個(gè)方法，并非一個(gè)算法！！

下面我先主要針對(duì)于動(dòng)態(tài)編程進(jìn)行一定的解釋說(shuō)明：

維基百科的意思大致是：動(dòng)態(tài)編程既是數(shù)學(xué)優(yōu)化方法又是計(jì)算機(jī)編程方法。該方法是由理查德·貝爾曼（Richard Bellman）在1950年代開發(fā)的，并且已在從航空工程到經(jīng)濟(jì)學(xué)的許多領(lǐng)域中得到應(yīng)用。在這兩種情況下，它都是指通過(guò)以遞歸方式將其分解為更簡(jiǎn)單的子問(wèn)題來(lái)簡(jiǎn)化一個(gè)復(fù)雜的問(wèn)題。盡管無(wú)法以這種方式解決某些決策問(wèn)題，但是跨越多個(gè)時(shí)間點(diǎn)的決策通常會(huì)遞歸拆分。同樣，在計(jì)算機(jī)科學(xué)中，如果可以通過(guò)將問(wèn)題分解為子問(wèn)題然后遞歸地找到子問(wèn)題的最優(yōu)解來(lái)最佳地解決問(wèn)題，則可以說(shuō)它具有最優(yōu)子結(jié)構(gòu)。

動(dòng)態(tài)編程的介紹

動(dòng)態(tài)編程是解決優(yōu)化問(wèn)題的最強(qiáng)大的設(shè)計(jì)技術(shù)。

分而治之算法將問(wèn)題劃分為不相交的子問(wèn)題，然后遞歸地解決子問(wèn)題，然后結(jié)合其解決方案來(lái)解決原始問(wèn)題。

當(dāng)子問(wèn)題不是獨(dú)立的時(shí)，例如當(dāng)它們共享相同的子問(wèn)題時(shí)，使用動(dòng)態(tài)編程。在這種情況下，分治法可能會(huì)做比必要的更多的工作，因?yàn)樗梢远啻谓鉀Q同一個(gè)子問(wèn)題。

動(dòng)態(tài)編程僅解決每個(gè)子問(wèn)題一次，并將結(jié)果存儲(chǔ)在表中，以便在需要時(shí)可以重復(fù)檢索它。

動(dòng)態(tài)編程是一種**自下而上的方法-**我們解決所有可能的小問(wèn)題，然后結(jié)合以獲得更大問(wèn)題的解決方案。

動(dòng)態(tài)規(guī)劃是一種算法設(shè)計(jì)的范式，其中，通過(guò)實(shí)現(xiàn)子問(wèn)題解決方案以及出現(xiàn)“ 最優(yōu)原理 ” 的組合來(lái)解決優(yōu)化問(wèn)題。

動(dòng)態(tài)編程的特點(diǎn)

當(dāng)問(wèn)題具有以下特征時(shí)，動(dòng)態(tài)編程將起作用：

• **最優(yōu)子結(jié)構(gòu)：**如果最優(yōu)解決方案包含最優(yōu)子解決方案，那么問(wèn)題將表現(xiàn)出最優(yōu)子結(jié)構(gòu)。
• **子問(wèn)題重疊：**當(dāng)遞歸算法將重復(fù)訪問(wèn)相同的子問(wèn)題時(shí)，則問(wèn)題將具有子問(wèn)題重疊。

如果問(wèn)題具有最佳子結(jié)構(gòu)，則可以遞歸定義最佳解決方案。如果問(wèn)題有重疊的子問(wèn)題，那么我們可以通過(guò)僅計(jì)算每個(gè)子問(wèn)題一次來(lái)改進(jìn)遞歸實(shí)現(xiàn)。

如果問(wèn)題沒(méi)有最佳子結(jié)構(gòu)，則沒(méi)有基礎(chǔ)來(lái)定義遞歸算法以找到最佳解決方案。如果一個(gè)問(wèn)題沒(méi)有重疊的子問(wèn)題，那么使用動(dòng)態(tài)編程就無(wú)濟(jì)于事。

如果子問(wèn)題的空間足夠大（即輸入大小為多項(xiàng)式），則動(dòng)態(tài)編程比遞歸更有效。

動(dòng)態(tài)編程的要素

基本上，三個(gè)要素是動(dòng)態(tài)編程算法的特征：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-SWAX3nC3-1584971186276)(https://static.javatpoint.com/tutorial/daa/images/elements-of-dynamic-programming.png)]

**子結(jié)構(gòu)：**將給定問(wèn)題分解為較小的子問(wèn)題。用較小問(wèn)題的解決方案來(lái)表達(dá)原始問(wèn)題的解決方案。

**表結(jié)構(gòu)：**解決了子問(wèn)題后，將結(jié)果存儲(chǔ)到表中的子問(wèn)題中。這樣做是因?yàn)樽訂?wèn)題解決方案已被多次重用，并且我們不想一遍又一遍地重復(fù)解決相同的問(wèn)題。

**自下而上的計(jì)算：**使用表格，將較小的子問(wèn)題的解決方案組合起來(lái)以解決較大的子問(wèn)題，并最終得出解決問(wèn)題的解決方案。

注意：自下而上是指：-

從最小的子問(wèn)題開始。

結(jié)合他們的解決方案，可以解決規(guī)模越來(lái)越大的子問(wèn)題。

直到解決原始問(wèn)題為止。

動(dòng)態(tài)編程的組成部分

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-Lzi92vLo-1584971186276)(https://static.javatpoint.com/tutorial/daa/images/components-of-dynamic-programming.png)]

**階段：**問(wèn)題可以分為幾個(gè)子問(wèn)題，稱為子階段。階段是給定問(wèn)題的一小部分。例如，在最短路徑問(wèn)題中，它們是由圖的結(jié)構(gòu)定義的。

狀態(tài)**：**每個(gè)階段都有幾個(gè)與之相關(guān)的狀態(tài)。最短路徑問(wèn)題的狀態(tài)是到達(dá)的節(jié)點(diǎn)。

**決策：**在每個(gè)階段，可以有多個(gè)選擇，應(yīng)從中做出最好的決定之一。在每個(gè)階段做出的決定都應(yīng)該是最佳的；這稱為階段決策。

**最優(yōu)政策：**這是一個(gè)決定每個(gè)階段決策的規(guī)則；如果策略是全局最優(yōu)的，則稱為最優(yōu)策略。這就是最佳貝爾曼原理。

給定當(dāng)前狀態(tài)，其余每個(gè)狀態(tài)的最佳選擇均不取決于先前的狀態(tài)或決策。在最短路徑問(wèn)題中，沒(méi)有必要僅知道我們?nèi)绾潍@得節(jié)點(diǎn)。

鑒于已經(jīng)解決了階段j + 1，存在一種遞歸關(guān)系，該關(guān)系確定階段j的最佳決策。

最后階段必須自己解決。

動(dòng)態(tài)規(guī)劃算法的發(fā)展

它可以分為四個(gè)步驟：

表征最佳解決方案的結(jié)構(gòu)。

遞歸定義最佳解決方案的值。像“分而治之”一樣，將問(wèn)題遞歸分為兩個(gè)或多個(gè)最佳部分。這有助于確定解決方案的外觀。

從下至上計(jì)算最佳解決方案的值（從最小的子問(wèn)題開始）

從較小的子問(wèn)題的計(jì)算值構(gòu)造整個(gè)問(wèn)題的最佳解決方案。

動(dòng)態(tài)編程的應(yīng)用

0/1背包問(wèn)題

數(shù)學(xué)優(yōu)化問(wèn)題

所有對(duì)最短路徑問(wèn)題

可靠性設(shè)計(jì)問(wèn)題

最長(zhǎng)公共子序列（LCS）

飛行控制和機(jī)器人控制

分時(shí)：它計(jì)劃作業(yè)以最大化CPU使用率

簡(jiǎn)單舉一個(gè)動(dòng)態(tài)編程的例子

太少寫算法的東西，所以這里以斐波那契做一個(gè)例子。后面舉幾個(gè)其他的例子，自行演示吧

斐波那契數(shù)是以下整數(shù)序列中的數(shù)字。

0，1，1，2，3，5，8，13，21，34，55，89，144，…

用數(shù)學(xué)術(shù)語(yǔ)來(lái)說(shuō)，斐波納契數(shù)的序列Fn由遞歸關(guān)系定義

F n = F n-1 + F n-2

具有種子值

F 0 = 0和F 1 = 1。

給定數(shù)字n，打印第n個(gè)斐波那契數(shù)。
例子：

輸入：n = 2 輸出1輸入：n = 9 輸出：34

方法1（使用遞歸）

一種簡(jiǎn)單的方法，它是上面給出的直接遞歸實(shí)現(xiàn)數(shù)學(xué)遞歸關(guān)系。

//Fibonacci Series using Recursion class fibonacci { static int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); } public static void main (String args[]) { int n = 9; System.out.println(fib(n)); } } /* This code is contributed by Rajat Mishra */

輸出量

34

時(shí)間復(fù)雜度： T（n）= T（n-1）+ T（n-2）是指數(shù)的。
我們可以觀察到該實(shí)現(xiàn)做了很多重復(fù)的工作（請(qǐng)參見下面的遞歸樹）。因此，對(duì)于第n個(gè)斐波那契數(shù)，這是一個(gè)錯(cuò)誤的實(shí)現(xiàn)。

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（0）

*額外空間：*如果考慮函數(shù)調(diào)用堆棧的大小，則為O（n），否則為O（1）。

方法2（使用動(dòng)態(tài)編程）
通過(guò)存儲(chǔ)到目前為止計(jì)算出的斐波那契數(shù)，我們可以避免方法1的重復(fù)工作。

// Fibonacci Series using Dynamic Programming class fibonacci { static int fib(int n) { /* Declare an array to store Fibonacci numbers. */int f[] = new int[n+2]; // 1 extra to handle case, n = 0 int i; /* 0th and 1st number of the series are 0 and 1*/f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { /* Add the previous 2 numbers in the series and store it */f[i] = f[i-1] + f[i-2]; } return f[n]; } public static void main (String args[]) { int n = 9; System.out.println(fib(n)); } } /* This code is contributed by Rajat Mishra */

當(dāng)然這只是使用動(dòng)態(tài)規(guī)劃進(jìn)行的優(yōu)化，具體優(yōu)化還有比如優(yōu)化空間、使用矩陣等方式。

其他高深的關(guān)于動(dòng)態(tài)規(guī)劃的算法自行百度吧。或者關(guān)注一下，等我下次有空專門來(lái)一篇。哈哈

其實(shí)根據(jù)上述的例子，你或許就有了一些想法和思路，沒(méi)錯(cuò)在整體的數(shù)據(jù)分析中，比如最近開展的智慧交通，我們難免在大量的數(shù)據(jù)中分析各種TopN，那么每次的查詢我們都要進(jìn)行重新的在大量的數(shù)據(jù)中進(jìn)行去取TopN嗎？我們能不能使用一個(gè)動(dòng)態(tài)規(guī)劃對(duì)程序進(jìn)行優(yōu)化，對(duì)每次的TopN進(jìn)行存儲(chǔ)，避免每次的重復(fù)工作。當(dāng)然不僅僅限于TopN的問(wèn)題。在編程和計(jì)算中均可以進(jìn)行應(yīng)用，這也是目前我覺(jué)得最簡(jiǎn)單的引用DP的方式。至于其他的后續(xù)再聊了。

我有一壺酒，足以慰風(fēng)塵。感覺(jué)對(duì)你有點(diǎn)幫助的話，給個(gè)關(guān)注唄！或者點(diǎn)個(gè)贊再走嘍！

參考資料：https://www.javatpoint.com/dynamic-programming-introduction

總結(jié)

以上是生活随笔為你收集整理的项目中要使用到动态规划该怎么应用，怎么说？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。