1. 動(dòng)態(tài)規(guī)劃的定義

百度百科的定義：在現(xiàn)實(shí)生活中，有一類活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。 因此各個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線．這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為多階段決策過(guò)程，這種問(wèn)題稱為多階段決策問(wèn)題。在多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，稱這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃方法。

動(dòng)態(tài)規(guī)劃問(wèn)題有以下特點(diǎn)：

1. 最優(yōu)子結(jié)構(gòu)性質(zhì)：如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，我們就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
2. 無(wú)后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說(shuō)，某狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
3. 子問(wèn)題重疊性質(zhì)：指在用遞歸算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次。

2.問(wèn)題引入

看完上面對(duì)于動(dòng)態(tài)規(guī)劃那么多文字，可能認(rèn)真看完也不會(huì)有深入的了解，我們來(lái)舉一個(gè)形象的例子：

2.1 青蛙跳臺(tái)階

劍指offer-10 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

碰到這種問(wèn)題，大家開(kāi)始想到的方法可能是枚舉的方法，n=1時(shí)，有1種；n=2時(shí)，11、2是2種；n=3時(shí)，111、12、21是3種；n=4時(shí)…（在這里把第n階臺(tái)階的走法次數(shù)記作dp[n]） 讀到這里，我提示大家一下，大家有沒(méi)有發(fā)現(xiàn)，我們?cè)谟?jì)算n=3時(shí)的dp[3]，重新把n=1和n=2的情況又算了一遍，或者說(shuō)，當(dāng)n=3時(shí)，只有兩種情況：

1. 第一種情況：n=1走再2步
2. 第二種情況：n=2走再走1步

所以，我們計(jì)算dp[3]時(shí)只需要計(jì)算dp[2]和dp[1],然后dp[3]=dp[2]+dp[1]，同理，我們可以得到如下遞推關(guān)系式：
d p [ n ] = d p [ n − 1 ] + d p [ n − 2 ] dp[n]=dp[n-1]+dp[n-2]
dp[n]=dp[n−1]+dp[n−2]

我們用了dp這個(gè)數(shù)組來(lái)存儲(chǔ)了每次的計(jì)算結(jié)果，我們?cè)偎鉪p[n]的時(shí)候只需要知道dp[n-1]和dp[n-2]即可，不需要再重復(fù)計(jì)算之前的臺(tái)階次數(shù)。

看一下這道題的解法：

def numWays(self, n: int) -> int:
        if n<=1:#n=0和1的時(shí)候都是1
            return 1
        elif n==2:#n=2的時(shí)候都是2
            return 2
        else:#上面兩部之所以要寫(xiě)的原因是因?yàn)閐p[0]和dp[1]是推導(dǎo)成功的兩個(gè)初始值。
            dp=[0 for i in range(n)]#創(chuàng)建一個(gè)長(zhǎng)度為n的數(shù)組用于存儲(chǔ)每次的dp[i]
            dp[0]=1
            dp[1]=2
            i=2
            while i<n:#循環(huán)計(jì)算每個(gè)dp[i]的值
                dp[i]=dp[i-1]+dp[i-2]
                i+=1
            a=int(dp[i-1])
            return a%1000000007#n=44后超出數(shù)據(jù)類型，數(shù)據(jù)會(huì)出錯(cuò)。

看一下運(yùn)行結(jié)果：

我們來(lái)總結(jié)一下：

• 觀察問(wèn)題是否可以由前面的階段推導(dǎo)出后面階段的關(guān)系式，因?yàn)檫@樣會(huì)節(jié)省大量重復(fù)的計(jì)算步驟。
• 定義一個(gè)數(shù)組或者序列來(lái)存儲(chǔ)每個(gè)階段需要存儲(chǔ)的值，比如我們采用d p [ i ] dp[i]dp[i]來(lái)存儲(chǔ)第i階樓梯會(huì)有多少種方式，這很重要，因?yàn)槲覀冃枰鞔_我們遞推的最小單元是什么。
• 確定遞推公式的初始值是什么，正如青蛙上臺(tái)階案例所說(shuō)的，我們的初始值是d p [ 0 ] dp[0]dp[0]和d p [ 1 ] dp[1]dp[1],分別代表著上1階臺(tái)階和上2階臺(tái)階的方法數(shù)。（0階臺(tái)階的方法數(shù)不是第一個(gè)元素）

2.2 買(mǎi)賣(mài)股票掙錢(qián)最多

讓我們?cè)賮?lái)看一道題：

leetcode-121: 給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。 你只能選擇 某一天 買(mǎi)入這只股票，并選擇在 未來(lái)的某一個(gè)不同的日子 賣(mài)出該股票。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。返回你可以從這筆交易中獲取的最大利潤(rùn)。如果你不能獲取任何利潤(rùn)，返回 0 。

例如： 輸入：[7,1,5,3,6,4] 輸出：5 解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出，最大利潤(rùn) = 6-1 = 5 。 注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格；同時(shí)，你不能在買(mǎi)入前賣(mài)出股票。

我們來(lái)分析一下，這道題利用雙循環(huán)即可解決，第一個(gè)循環(huán)用來(lái)表示當(dāng)前股票的價(jià)格i，第二個(gè)循環(huán)用來(lái)記錄在當(dāng)前股票價(jià)格為i下，后面的天賣(mài)出股票能獲得的最大利潤(rùn)，這樣的話時(shí)間復(fù)雜度為 O ( n 2 ) O(n^2) O(n2)

動(dòng)態(tài)規(guī)劃思想：我們將這個(gè)問(wèn)題換個(gè)角度思考

• 舊：我們前面利用雙循環(huán)的含義是在當(dāng)天的價(jià)格下買(mǎi)入，后面的天賣(mài)出所能獲取的最大利潤(rùn)為多少？
• 新：當(dāng)時(shí)間來(lái)到第i天，能掙的最大利潤(rùn)為多少？（這里指的第i天的最大利潤(rùn)，不是指在第i天賣(mài)出，是到第i天為止，所能賣(mài)出的最大利潤(rùn)）

以新的想法，我們就需要知道在第i天賣(mài)出股票時(shí)，和第i-1天賣(mài)出的股票最大利潤(rùn)相比哪個(gè)時(shí)間掙得多？聲明dp[i]為在第i天時(shí)，股票所能獲取的最大利潤(rùn)，那么我們就會(huì)出現(xiàn)如下表達(dá)式： d p [ i ] = m a x ( n u m [ i ] − m i n p r i c e , d p [ i − 1 ] ) dp[i]=max(num[i]-minprice,dp[i-1]) dp[i]=max(num[i]−minprice,dp[i−1])

解釋一下變量：

• dp[i]是指到了第i天，所能獲取的最大利潤(rùn)，例如股票的價(jià)格是[1,2,4,1],那么d p [ 0 ] = 0 , d p [ 1 ] = 1 , d p [ 2 ] = 3 , d p [ 3 ] = 3 dp[0]=0,dp[1]=1,dp[2]=3,dp[3]=3dp[0]=0,dp[1]=1,dp[2]=3,dp[3]=3，這里dp[3]也等于3的原因是：第4天價(jià)格為1，d p [ 3 ] = m a x ( 1 − 1 , d p [ 2 ] ) = 3 dp[3]=max(1-1,dp[2])=3dp[3]=max(1−1,dp[2])=3
• 我們所要比較的就是第i天所能獲取的最大利潤(rùn)和第i-1天所能獲取的最大利潤(rùn)。哪個(gè)大，哪個(gè)就是第i天所能獲取的最大利潤(rùn)。

我們又找到了遞推公式： d p [ i ] = m a x ( n u m [ i ] − m i n p r i c e , d p [ i − 1 ] ) dp[i]=max(num[i]-minprice,dp[i-1]) dp[i]=max(num[i]−minprice,dp[i−1]) 我們只要找到minprice即可。

最終代碼如下：

def maxProfit(self, prices: List[int]) -> int:
        n=len(prices)
        dp=[0 for i in range(n)]#構(gòu)造dp[]
        dp[0]=0#dp[i]的初始值
        minprice=prices[0]
        maxp=0
        i=1
        while i<n:
            minprice=min(minprice,prices[i])#到第i天股票的歷史最低價(jià)是多少
            dp[i]=max(prices[i]-minprice,dp[i-1])#計(jì)算第i天為止最高利潤(rùn)
            maxp=max(maxp,dp[i])#計(jì)算最高利潤(rùn)
            i+=1
        return maxp

結(jié)果如下：

2.3 機(jī)器人尋路問(wèn)題

leetcode:62. 不同路徑 一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。問(wèn)總共有多少條不同的路徑？

這道題就留給大家思考吧，需要注意以下幾個(gè)點(diǎn)：

• 這是一個(gè)二維dp[]
• 如何實(shí)現(xiàn)只往下或者右走？
• 遞推關(guān)系式是什么？
• 初始值是什么？

3. 總結(jié)

動(dòng)態(tài)規(guī)劃解決問(wèn)題對(duì)看問(wèn)題的角度有著獨(dú)特的方式，開(kāi)始學(xué)習(xí)可能會(huì)覺(jué)得別扭，但是經(jīng)過(guò)一些題的訓(xùn)練，你就會(huì)找到最優(yōu)子結(jié)構(gòu)、無(wú)后效性等動(dòng)態(tài)規(guī)劃的特征，總而言之，多理解，多動(dòng)手練習(xí)，動(dòng)態(tài)規(guī)劃不是問(wèn)題！

到此這篇關(guān)于淺談python數(shù)據(jù)結(jié)構(gòu)之動(dòng)態(tài)規(guī)劃的文章就介紹到這了,更多相關(guān)python動(dòng)態(tài)規(guī)劃內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論