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

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

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

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

2.問題引入

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

2.1 青蛙跳臺階

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

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

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

所以，我們計(jì)算dp[3]時只需要計(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這個數(shù)組來存儲了每次的計(jì)算結(jié)果，我們再算dp[n]的時候只需要知道dp[n-1]和dp[n-2]即可，不需要再重復(fù)計(jì)算之前的臺階次數(shù)。

看一下這道題的解法：

def numWays(self, n: int) -> int:
        if n<=1:#n=0和1的時候都是1
            return 1
        elif n==2:#n=2的時候都是2
            return 2
        else:#上面兩部之所以要寫的原因是因?yàn)閐p[0]和dp[1]是推導(dǎo)成功的兩個初始值。
            dp=[0 for i in range(n)]#創(chuàng)建一個長度為n的數(shù)組用于存儲每次的dp[i]
            dp[0]=1
            dp[1]=2
            i=2
            while i<n:#循環(huán)計(jì)算每個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ù)會出錯。

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

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

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

2.2 買賣股票掙錢最多

讓我們再來看一道題：

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

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

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

動態(tài)規(guī)劃思想：我們將這個問題換個角度思考

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

以新的想法，我們就需要知道在第i天賣出股票時，和第i-1天賣出的股票最大利潤相比哪個時間掙得多？聲明dp[i]為在第i天時，股票所能獲取的最大利潤，那么我們就會出現(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天，所能獲取的最大利潤，例如股票的價格是[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天價格為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天所能獲取的最大利潤和第i-1天所能獲取的最大利潤。哪個大，哪個就是第i天所能獲取的最大利潤。

我們又找到了遞推公式： 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天股票的歷史最低價是多少
            dp[i]=max(prices[i]-minprice,dp[i-1])#計(jì)算第i天為止最高利潤
            maxp=max(maxp,dp[i])#計(jì)算最高利潤
            i+=1
        return maxp

結(jié)果如下：

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

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

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

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

3. 總結(jié)

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

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

最新評論