《動態(tài)規(guī)劃應(yīng)用舉例》課件

動態(tài)規(guī)劃應(yīng)用舉例CATALOGUE目錄動態(tài)規(guī)劃簡介動態(tài)規(guī)劃的算法流程動態(tài)規(guī)劃應(yīng)用舉例-背包問題動態(tài)規(guī)劃應(yīng)用舉例-最長公共子序列動態(tài)規(guī)劃應(yīng)用舉例-斐波那契數(shù)列動態(tài)規(guī)劃應(yīng)用舉例-樹的最大/最小路徑和問題CHAPTER動態(tài)規(guī)劃簡介01動態(tài)規(guī)劃的定義動態(tài)規(guī)劃是一種通過將問題分解為相互重疊的子問題，并存儲子問題的解以避免重復(fù)計算，從而高效地解決優(yōu)化問題的算法。它是一種通過將原問題分解為相對簡單的子問題，并從子問題的最優(yōu)解逐步構(gòu)造出原問題的最優(yōu)解的方法。通過自底向上的方式求解子問題，逐步構(gòu)造出原問題的最優(yōu)解。通常采用遞歸方式實現(xiàn)，但遞歸可能導(dǎo)致大量的重復(fù)計算，因此需要使用備忘錄或記憶化技術(shù)來存儲已解決的子問題。將問題分解為子問題，并存儲子問題的解，避免重復(fù)計算。動態(tài)規(guī)劃的基本思想03狀態(tài)轉(zhuǎn)移方程動態(tài)規(guī)劃適用于具有狀態(tài)轉(zhuǎn)移方程的問題，即當前狀態(tài)依賴于前一狀態(tài)和當前決策。01最優(yōu)化問題動態(tài)規(guī)劃適用于求解最優(yōu)化問題，如最大值、最小值、最長路徑等。02子問題重疊動態(tài)規(guī)劃適用于子問題重疊的情況，即子問題之間存在共享的狀態(tài)或決策。動態(tài)規(guī)劃的適用場景CHAPTER動態(tài)規(guī)劃的算法流程02將問題劃分為若干個階段，每個階段都有自己的狀態(tài)和決策。階段劃分應(yīng)使問題的求解過程清晰明了，便于分析和求解。階段劃分定義每個階段的狀態(tài)，狀態(tài)應(yīng)能夠完全描述該階段的問題。狀態(tài)應(yīng)具有可轉(zhuǎn)移性，即從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)是可能的。狀態(tài)定義根據(jù)問題的性質(zhì)和階段劃分，建立狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移方程描述了從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)的過程和條件。狀態(tài)轉(zhuǎn)移方程優(yōu)化子結(jié)構(gòu)將問題分解為若干個子問題，每個子問題都有自己的最優(yōu)解。子問題的最優(yōu)解應(yīng)能夠通過狀態(tài)轉(zhuǎn)移方程相互關(guān)聯(lián)，以便求解整個問題的最優(yōu)解。根據(jù)狀態(tài)轉(zhuǎn)移方程和優(yōu)化子結(jié)構(gòu)，建立最優(yōu)解的遞推關(guān)系。最優(yōu)解的遞推關(guān)系描述了如何從子問題的最優(yōu)解逐步推導(dǎo)出整個問題的最優(yōu)解。最優(yōu)解的遞推關(guān)系CHAPTER動態(tài)規(guī)劃應(yīng)用舉例-背包問題03問題描述背包問題是一個經(jīng)典的優(yōu)化問題，其目標是在給定一定重量的背包和一組物品的情況下，選擇合適的物品放入背包，使得背包中物品的總價值最大。02物品可能有不同的重量和價值，每種物品的數(shù)量也是有限的。03問題是如何選擇物品，使得在不超過背包承重限制的前提下，所裝物品的總價值最大。01VSdp[i][j]表示在前i個物品中選，總重量不超過j的條件下，能夠獲得的最大價值。狀態(tài)轉(zhuǎn)移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])，其中w[i]表示第i個物品的重量，v[i]表示第i個物品的價值。狀態(tài)定義狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程VS最優(yōu)解的遞推關(guān)系基于狀態(tài)轉(zhuǎn)移方程，通過逐步計算dp數(shù)組的值，最終得到最大價值。在計算過程中，需要保留已經(jīng)計算過的dp值，以便在計算后續(xù)狀態(tài)時使用。最優(yōu)解的遞推關(guān)系算法實現(xiàn)主要包括初始化dp數(shù)組、填充dp數(shù)組和返回最大價值三個步驟。返回最大價值時，返回dp[n][W]的值，其中n是物品數(shù)量，W是背包承重限制。初始化dp數(shù)組時，需要為每個物品和重量組合設(shè)置一個初始值，通常為0或負無窮大。填充dp數(shù)組時，需要按照狀態(tài)轉(zhuǎn)移方程逐步計算每個狀態(tài)的值。算法實現(xiàn)CHAPTER動態(tài)規(guī)劃應(yīng)用舉例-最長公共子序列04給出兩個序列A和B，找出兩個序列的最長公共子序列。最長公共子序列是指兩個序列中同時出現(xiàn)的最長的子序列。問題描述定義狀態(tài)dp[i][j]表示A的前i個字符和B的前j個字符的最長公共子序列的長度。狀態(tài)轉(zhuǎn)移方程：dp[i][j]=max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1。狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程最優(yōu)解的遞推關(guān)系是：如果A[i-1]等于B[j-1]，則dp[i][j]=dp[i-1][j-1]+1；否則dp[i][j]=max(dp[i][j-1],dp[i-1][j])+1。最優(yōu)解的遞推關(guān)系初始化dp數(shù)組，dp[0][j]=0，dp[i][0]=0，dp[i][j]=-1（如果A[i]和B[j]不相等）。從i=1到m，j=1到n，根據(jù)狀態(tài)轉(zhuǎn)移方程更新dp數(shù)組。在dp數(shù)組中，最長公共子序列的長度即為dp[m][n]，回溯dp數(shù)組找出最長公共子序列的具體字符。算法實現(xiàn)CHAPTER動態(tài)規(guī)劃應(yīng)用舉例-斐波那契數(shù)列05斐波那契數(shù)列是一個經(jīng)典的數(shù)列問題，其中每個數(shù)字是前兩個數(shù)字的和。給定一個正整數(shù)n，要求找出斐波那契數(shù)列的第n項。問題描述01為了解決這個問題，我們可以使用動態(tài)規(guī)劃來定義狀態(tài)和狀態(tài)轉(zhuǎn)移方程。假設(shè)dp[i]表示斐波那契數(shù)列的第i項，則狀態(tài)轉(zhuǎn)移方程如下02dp[i]=dp[i-1]+dp[i-2]03初始條件為：dp[0]=0，dp[1]=1。狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程通過狀態(tài)轉(zhuǎn)移方程，我們可以推導(dǎo)出最優(yōu)解的遞推關(guān)系。由于dp[i]=dp[i-1]+dp[i-2]，我們可以發(fā)現(xiàn)dp[i]的值依賴于dp[i-1]和dp[i-2]。因此，我們可以使用最優(yōu)子結(jié)構(gòu)的方法來遞推求解。最優(yōu)解的遞推關(guān)系算法實現(xiàn)以下是使用Python實現(xiàn)的動態(tài)規(guī)劃算法算法實現(xiàn)010203deffibonacci(n)dp=[0,1]+[0]*(n-1)#初始化狀態(tài)數(shù)組```pythonforiinrange(2,n+1)dp[i]=dp[i-1]+dp[i-2]#狀態(tài)轉(zhuǎn)移方程returndp[n]#返回第n項的值算法實現(xiàn)```這個算法的時間復(fù)雜度為O(n)，空間復(fù)雜度也為O(n)。算法實現(xiàn)CHAPTER動態(tài)規(guī)劃應(yīng)用舉例-樹的最大/最小路徑和問題06樹的最大/最小路徑和問題是指給定一棵樹，找出從根節(jié)點到葉子節(jié)點的最大/最小路徑和。這里的路徑是指從根節(jié)點到葉子節(jié)點的所有節(jié)點連成的序列，路徑和是指該路徑上所有節(jié)點的值之和。問題描述狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程對于樹中的每個節(jié)點，我們定義其狀態(tài)為該節(jié)點到葉子節(jié)點的路徑和。對于根節(jié)點，其狀態(tài)為該節(jié)點的值。對于其他節(jié)點，其狀態(tài)為其子節(jié)點的狀態(tài)中的最大/最小值加上該節(jié)點的值。狀態(tài)轉(zhuǎn)移方程為：dp[i]=max/min(dp[j]+v[i])，其中v[i]表示節(jié)點i的值，dp[j]表示節(jié)點j的狀態(tài)，j表示節(jié)點i的子節(jié)點。最優(yōu)解的遞推關(guān)系為：最優(yōu)解=max/min(dp[i]+v[i])，其中v[i]表示葉子節(jié)點的值，dp[i]表示葉子節(jié)點的狀態(tài)。最優(yōu)解的遞推關(guān)系算法實現(xiàn)