一、概念起源

??動(dòng)態(tài)規(guī)劃，又名DP算法（取自其Dynamic Programming的縮寫），最初是運(yùn)籌學(xué)的一個(gè)分支，是用來(lái)求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。

二、基本思想

??把 多階段過(guò)程 轉(zhuǎn)化為一系列單階段過(guò)程，利用各階段之間的關(guān)系，逐個(gè)求解。那什么叫多階段過(guò)程呢？

多階段過(guò)程：首先大家可以思考一下以下這個(gè)問(wèn)題：

假如我們有面值為1元/3元/5元的硬幣若干枚，如何用最少的硬幣湊夠137元？

當(dāng)然我們可以使用暴力枚舉解決這個(gè)問(wèn)題，不夠那樣復(fù)雜度就太高了。我們可以這樣考慮，湊齊137元可以看成一個(gè)最終目標(biāo)，我們可以把它細(xì)分為先以最少的硬幣數(shù)量湊齊136元（這樣再加1元就137元了）或是133元或是132元 + 1次。然后我們的問(wèn)題轉(zhuǎn)變?yōu)榱讼纫宰钌俚挠矌艛?shù)量湊齊136元或是133元或是132元。看似問(wèn)題數(shù)量變更多了，但是實(shí)際問(wèn)題難度卻變小了。
而且這種細(xì)分方式可以不斷細(xì)分，一直細(xì)分到接近于0元。而在這個(gè)思維過(guò)程中，我們就是將解決137元的問(wèn)題分階段的完成，而這個(gè)過(guò)程就叫做 多階段過(guò)程 。

三、解題步驟(思路)

利用動(dòng)態(tài)規(guī)劃思想從上往下思考問(wèn)題：將多階段問(wèn)題轉(zhuǎn)變成更小的多階段問(wèn)題（狀態(tài)轉(zhuǎn)移方程）

分解至最小的單階段問(wèn)題（可直接解決問(wèn)題）。

利用循環(huán)從下往上解決問(wèn)題。

四、算法框架

相對(duì)于其他基本算法，動(dòng)態(tài)規(guī)劃算法比較靈活，其主體框架取決于其具體問(wèn)題，具體問(wèn)題決定具體的狀態(tài)轉(zhuǎn)移方程；因此，其不像回溯法有一套“亙古不變”的算法框架；所以以下的算法只能說(shuō)是解決類似上述硬幣問(wèn)題的DP算法框架，只能算是給各位拋磚引玉。

?變量解釋：

??res：存儲(chǔ)各階段問(wèn)題的答案

??n：最終問(wèn)題的標(biāo)記位

??i：循環(huán)的索引

??f：某階段問(wèn)題的答案與前些階段問(wèn)題答案之間的函數(shù)關(guān)系

void dp(int n) {// 定義問(wèn)題的解數(shù)組int res[n + 1];// 初始化最小的單階段問(wèn)題的解res[1] = 1 ...// 從初始化后的解數(shù)組的第一個(gè)位置開始循環(huán)計(jì)算res[i]int i = inital;while (i <= n) {// f函數(shù)取決于狀態(tài)轉(zhuǎn)移方程res[i] = f(res[i - 1], res[i - 2], res[i - 3]...);i++;}return res[n]; }

五、經(jīng)典實(shí)現(xiàn)

經(jīng)典問(wèn)題：Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

int maxProfit(int* prices, int pricesSize) {if (pricesSize == 0) {return 0;}int res[pricesSize];int min[pricesSize];res[0] = 0;min[0] = prices[0];int i = 1;while (i < pricesSize) {if (res[i - 1] < prices[i] - min[i - 1]) {res[i] = prices[i] - min[i - 1];} else {res[i] = res[i - 1];}if (prices[i] < min[i - 1]) {min[i] = prices[i];} else {min[i] = min[i - 1];}i++;}return res[pricesSize - 1]; }

轉(zhuǎn)載于:https://www.cnblogs.com/codernie/p/9085180.html

總結(jié)

以上是生活随笔為你收集整理的五大经典算法之动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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