《動態(tài)規(guī)劃類算法》課件

動態(tài)規(guī)劃類算法動態(tài)規(guī)劃算法是一種解決優(yōu)化問題的方法，它將問題分解成子問題，并利用子問題的解來構(gòu)建最終解。什么是動態(tài)規(guī)劃核心思想將復(fù)雜問題分解成更小的子問題，并存儲子問題的解，以避免重復(fù)計算。優(yōu)化策略通過記錄已解決子問題的解，動態(tài)規(guī)劃可以有效地避免重復(fù)計算，提高算法效率。動態(tài)規(guī)劃的基本思想將復(fù)雜問題分解為子問題存儲子問題的解，避免重復(fù)計算自底向上，逐步構(gòu)建最優(yōu)解動態(tài)規(guī)劃問題的特點1最優(yōu)子結(jié)構(gòu)問題的最優(yōu)解可以由子問題的最優(yōu)解組合而成。2重疊子問題在求解過程中，會多次遇到相同的子問題。3無后效性子問題的解一旦確定，就不會再改變。動態(tài)規(guī)劃算法的基本步驟定義狀態(tài)確定問題的子問題，并定義一個狀態(tài)變量來表示子問題的結(jié)果。例如，在計算斐波那契數(shù)列中，狀態(tài)變量可以表示第n個斐波那契數(shù)。確定初始狀態(tài)確定一些最基本子問題的解，并將其作為初始狀態(tài)值。例如，在斐波那契數(shù)列中，f(0)=0,f(1)=1。建立狀態(tài)轉(zhuǎn)移方程找出當(dāng)前狀態(tài)的值如何由之前的狀態(tài)計算得出。例如，在斐波那契數(shù)列中，f(n)=f(n-1)+f(n-2)。計算最終結(jié)果根據(jù)狀態(tài)轉(zhuǎn)移方程遞歸地計算所有狀態(tài)的值，最終得到問題的解。如何建立動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程定義子問題首先要確定問題的子問題，即狀態(tài)。尋找遞推關(guān)系找到當(dāng)前子問題的解與之前子問題的解之間的關(guān)系。建立狀態(tài)轉(zhuǎn)移方程將遞推關(guān)系用數(shù)學(xué)公式表示出來，即狀態(tài)轉(zhuǎn)移方程。動態(tài)規(guī)劃算法的時間復(fù)雜度O(N)線性復(fù)雜度例如，斐波那契數(shù)列的動態(tài)規(guī)劃實現(xiàn)。O(N^2)平方復(fù)雜度例如，最長公共子序列的動態(tài)規(guī)劃實現(xiàn)。O(N*M)二維復(fù)雜度例如，01背包問題的動態(tài)規(guī)劃實現(xiàn)。動態(tài)規(guī)劃的基本模型斐波那契數(shù)列計算第n個斐波那契數(shù)，經(jīng)典的動態(tài)規(guī)劃問題。湊零錢問題給定不同面額的硬幣和一個總金額，求最少硬幣數(shù)量的組合。最長公共子序列找出兩個字符串的最長公共子序列。01背包問題給定容量為W的背包和n個物品，每個物品有重量和價值，求背包所能裝的最大價值。斐波那契數(shù)列斐波那契數(shù)列是一個經(jīng)典的動態(tài)規(guī)劃問題。它定義為：F(0)=0，F(xiàn)(1)=1，F(xiàn)(n)=F(n-1)+F(n-2)(n>=2)。動態(tài)規(guī)劃的思路是：利用之前計算過的結(jié)果來加速當(dāng)前狀態(tài)的計算，避免重復(fù)計算。湊零錢問題假設(shè)你有一個裝滿了硬幣的錢包，每種硬幣都有無限個。你想要找到用這些硬幣湊成特定金額的最少硬幣數(shù)量。例如，如果你需要湊出11美元，并且你的錢包里有1美元、2美元、5美元和10美元的硬幣，那么最少需要用3枚硬幣來湊成11美元（一枚10美元硬幣和一枚1美元硬幣）。最長公共子序列定義一個序列S的子序列是指從S中刪除若干個字符后剩余的字符序列，例如，"ABCBDAB"的子序列有"ABAD","BCDA"等，而"ACBD"不是子序列。給定兩個字符串X和Y，求解X和Y的最長公共子序列(LongestCommonSubsequence,LCS)，即長度最大的公共子序列。應(yīng)用LCS問題廣泛應(yīng)用于生物信息學(xué)、文本編輯、軟件工程等領(lǐng)域。例如，在DNA序列比對中，LCS可以用來識別兩個DNA序列的相似性。01背包問題給定一個容量為W的背包，和N個物品。每個物品有兩個屬性：價值Vi和重量Wi。問如何選擇物品放入背包，使得背包中物品的總價值最大。01背包問題要求對于每個物品，只有兩種選擇：選或者不選，不能選擇部分物品。完全背包問題完全背包問題是動態(tài)規(guī)劃中一個經(jīng)典問題，它允許物品可以無限次地被放入背包中。給定一個容量為W的背包和n個物品，每個物品都有重量wi和價值vi，求解如何選擇物品放入背包中，使得背包中物品的總價值最大。最長遞增子序列最長遞增子序列問題是指在一個序列中找到最長的遞增子序列。例如，序列{1,3,2,4,5}的最長遞增子序列為{1,2,4,5}。該問題可以采用動態(tài)規(guī)劃的思想來解決，將最長遞增子序列問題分解成子問題，然后使用子問題的解來解決原問題。最短路徑問題導(dǎo)航應(yīng)用程序從起點到終點找到最佳路線。網(wǎng)絡(luò)路由在網(wǎng)絡(luò)中找到數(shù)據(jù)包傳輸?shù)淖疃搪窂健＞庉嬀嚯x問題編輯距離，又稱為萊文斯坦距離，用于衡量兩個字符串之間的差異程度。它指的是將一個字符串轉(zhuǎn)換為另一個字符串所需的最少編輯操作次數(shù)，包括插入、刪除和替換。狀態(tài)壓縮動態(tài)規(guī)劃將狀態(tài)信息壓縮成一個整數(shù)表示，用于存儲狀態(tài)信息。利用位運算進行狀態(tài)壓縮，提高算法效率。常用于解決一些與集合相關(guān)的動態(tài)規(guī)劃問題。樹形動態(tài)規(guī)劃樹形結(jié)構(gòu)樹形動態(tài)規(guī)劃適用于解決樹形結(jié)構(gòu)上的問題，通常需要對每個節(jié)點進行遍歷和計算。狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移方程通常依賴于子節(jié)點的信息，通過自底向上或自頂向下的方式進行動態(tài)規(guī)劃計算。區(qū)間動態(tài)規(guī)劃定義區(qū)間動態(tài)規(guī)劃通常用于解決與區(qū)間相關(guān)的優(yōu)化問題，例如求解最優(yōu)區(qū)間劃分、最長公共子序列等問題。這種方法通過將整個區(qū)間劃分為多個子區(qū)間，遞歸地求解子區(qū)間的最優(yōu)解，最終合并得到全局最優(yōu)解。特點區(qū)間動態(tài)規(guī)劃通常使用一個二維數(shù)組dp[i][j]來存儲從i到j(luò)區(qū)間的最優(yōu)解，其中i和j分別代表區(qū)間的起點和終點。狀態(tài)轉(zhuǎn)移方程通常是根據(jù)子區(qū)間的最優(yōu)解遞歸定義的。應(yīng)用區(qū)間動態(tài)規(guī)劃廣泛應(yīng)用于各種領(lǐng)域，例如字符串處理、序列比對、圖像處理等。例如，最長公共子序列問題，可以通過區(qū)間動態(tài)規(guī)劃方法高效地求解。位運算優(yōu)化動態(tài)規(guī)劃1狀態(tài)壓縮將集合或狀態(tài)表示成二進制數(shù)，用位運算進行狀態(tài)的枚舉和轉(zhuǎn)移。2效率提升位運算比傳統(tǒng)的循環(huán)枚舉更高效，可大幅減少代碼量，提高算法速度。3適用場景適用于狀態(tài)空間較小，且狀態(tài)之間存在相互依賴關(guān)系的問題。多重背包問題每個物品有多個，例如3個蘋果，2個梨。需要考慮每個物品的數(shù)量限制，并尋找最優(yōu)的裝包方案?？梢杂脛討B(tài)規(guī)劃解決，需要將物品數(shù)量作為狀態(tài)的一維。字符串動態(tài)規(guī)劃子串匹配例如，判斷字符串s是否包含字符串t。最長公共子串例如，求兩個字符串的最長公共子串。編輯距離例如，求兩個字符串之間的編輯距離。數(shù)位動態(tài)規(guī)劃1數(shù)字范圍限制適用于統(tǒng)計滿足特定條件的數(shù)字個數(shù)，例如在給定范圍內(nèi)，統(tǒng)計所有包含特定數(shù)字的數(shù)字的個數(shù)。2狀態(tài)定義與轉(zhuǎn)移通常使用dp[i][j]表示從高位到第i位，且當(dāng)前位數(shù)字為j的所有數(shù)字的個數(shù)。3邊界條件處理需要根據(jù)具體問題設(shè)置邊界條件，例如第一個數(shù)字是否可以為0，是否允許前導(dǎo)零等。概率動態(tài)規(guī)劃概率轉(zhuǎn)移概率動態(tài)規(guī)劃基于概率轉(zhuǎn)移，將問題分解為多個子問題，每個子問題都有不同的概率。期望值通過計算每個子問題的期望值，最終得到整個問題的期望值。應(yīng)用場景概率動態(tài)規(guī)劃廣泛應(yīng)用于金融、游戲、生物信息學(xué)等領(lǐng)域。股票買賣問題最佳買賣時機在給定的時間范圍內(nèi)，找到買入和賣出股票的最佳時機，以最大化利潤。交易次數(shù)限制可能限制交易次數(shù)，例如只能進行一次交易或最多兩次交易。冷凍期在賣出股票后，可能需要等待一定時間才能再次買入。子集背包問題子集選擇從所有物品中選擇一個子集，使總價值最大。容量限制子集的總重量不能超過背包的容量。動態(tài)規(guī)劃求解利用動態(tài)規(guī)劃，枚舉所有子集，找到最優(yōu)解。泰波那契數(shù)列泰波那契數(shù)列類似于斐波那契數(shù)列，但它以三個初始值開始，每個后續(xù)數(shù)字是前三個數(shù)字之和。例如，泰波那契數(shù)列的前幾個項是：0、1、1、2、4、7、13、24、44、81。數(shù)塔問題描述一個數(shù)字金字塔，從塔頂開始，每次可以向下移動到下一層的相鄰位置，求從塔頂?shù)剿椎穆窂降淖畲髷?shù)字和。思路從塔底向上遞推，每個位置的數(shù)字和等于其下面兩個位置的最大數(shù)字和加上當(dāng)前位置的值，最終得到塔頂位置的最大數(shù)字和。最小生成樹問題最小生成樹(MST)問題是在一個帶權(quán)無向圖中尋找一棵包含所有頂點的生成樹，且樹的總權(quán)重最小。常用的算法有Kruskal算法和Prim算法。Kruskal算法基于貪心策略，每次選擇權(quán)重最小的邊，并加入到生成樹中，直到所有頂點都被連接。Prim算法從一個頂點開始，每次選擇權(quán)重最小的邊，并連接到生成樹中，直到所有頂點都被連接。單調(diào)隊列優(yōu)化動態(tài)規(guī)劃單調(diào)隊列優(yōu)化在動態(tài)規(guī)劃中，當(dāng)狀態(tài)轉(zhuǎn)移方程需要用到之前若干個狀態(tài)的值時，可以使用單調(diào)隊列來優(yōu)化。時間復(fù)雜度通過維護一個單調(diào)隊列，可以將狀態(tài)轉(zhuǎn)移