《－動(dòng)態(tài)規(guī)劃》課件

動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃是一種算法設(shè)計(jì)技術(shù)。它將復(fù)雜問(wèn)題分解成更小的子問(wèn)題。通過(guò)存儲(chǔ)子問(wèn)題的解，避免重復(fù)計(jì)算，提高效率。廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)等領(lǐng)域。動(dòng)態(tài)規(guī)劃的基本思想分解問(wèn)題將復(fù)雜問(wèn)題分解為更小的子問(wèn)題。解決子問(wèn)題從最小的子問(wèn)題開始，逐步解決。存儲(chǔ)結(jié)果將子問(wèn)題的解存儲(chǔ)起來(lái)，避免重復(fù)計(jì)算。組合結(jié)果利用子問(wèn)題的解，構(gòu)建最終問(wèn)題的解。動(dòng)態(tài)規(guī)劃的適用場(chǎng)景優(yōu)化問(wèn)題求解最優(yōu)解，如最短路徑、最大收益、最小成本等。組合問(wèn)題從多個(gè)選項(xiàng)中選擇最佳方案，如背包問(wèn)題、硬幣找零問(wèn)題等。博弈問(wèn)題分析博弈雙方策略，找到最佳策略，如棋類游戲、拍賣等。圖論問(wèn)題解決圖相關(guān)的最優(yōu)路徑問(wèn)題，如最短路徑問(wèn)題、最小生成樹問(wèn)題等。動(dòng)態(tài)規(guī)劃的工作流程1定義問(wèn)題明確問(wèn)題目標(biāo)和約束條件2構(gòu)建狀態(tài)確定狀態(tài)表示，將問(wèn)題分解為子問(wèn)題3狀態(tài)轉(zhuǎn)移方程定義狀態(tài)之間的關(guān)系，描述如何從子問(wèn)題推導(dǎo)出最終解4邊界條件確定遞歸終止條件，防止無(wú)限循環(huán)5計(jì)算結(jié)果自底向上或自頂向下計(jì)算最優(yōu)解記憶化搜索避免重復(fù)計(jì)算記憶化搜索是一種結(jié)合了遞歸和動(dòng)態(tài)規(guī)劃思想的優(yōu)化方法，通過(guò)保存已計(jì)算結(jié)果，避免重復(fù)計(jì)算。探索路徑記憶化搜索如同登山，將已登頂?shù)穆肪€記錄下來(lái)，下次只需沿著已知路線前進(jìn)。樹形結(jié)構(gòu)記憶化搜索在本質(zhì)上類似于對(duì)樹形結(jié)構(gòu)的遍歷，通過(guò)記憶已訪問(wèn)的節(jié)點(diǎn)，避免重復(fù)搜索相同節(jié)點(diǎn)。動(dòng)態(tài)規(guī)劃的三大要素最優(yōu)子結(jié)構(gòu)問(wèn)題可以分解為更小的子問(wèn)題，子問(wèn)題的最優(yōu)解可以組合成原問(wèn)題的最優(yōu)解。這意味著可以遞歸地解決問(wèn)題，將復(fù)雜的問(wèn)題分解成更小的、更容易解決的問(wèn)題。重疊子問(wèn)題在求解過(guò)程中，會(huì)重復(fù)計(jì)算相同的子問(wèn)題。動(dòng)態(tài)規(guī)劃通過(guò)存儲(chǔ)子問(wèn)題的解，避免重復(fù)計(jì)算，提高效率。這意味著可以將子問(wèn)題的解存儲(chǔ)在一個(gè)表中，以便在需要時(shí)快速訪問(wèn)。狀態(tài)轉(zhuǎn)移方程定義一個(gè)遞歸關(guān)系，描述如何從子問(wèn)題的解推導(dǎo)出原問(wèn)題的解。狀態(tài)轉(zhuǎn)移方程是動(dòng)態(tài)規(guī)劃的核心，它定義了如何從子問(wèn)題得到最終解。每個(gè)子問(wèn)題都對(duì)應(yīng)一個(gè)狀態(tài)，狀態(tài)轉(zhuǎn)移方程描述了狀態(tài)之間的轉(zhuǎn)換關(guān)系。最優(yōu)子結(jié)構(gòu)定義如果一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解，則該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。例如，在求解最短路徑問(wèn)題時(shí)，最短路徑一定包含其子路徑的最短路徑。重要性最優(yōu)子結(jié)構(gòu)是動(dòng)態(tài)規(guī)劃問(wèn)題的關(guān)鍵特征之一，它確保了我們可以在子問(wèn)題上進(jìn)行遞歸求解，最終得到全局最優(yōu)解。應(yīng)用識(shí)別問(wèn)題是否具有最優(yōu)子結(jié)構(gòu)是應(yīng)用動(dòng)態(tài)規(guī)劃解決問(wèn)題的首要步驟。重疊子問(wèn)題子問(wèn)題重復(fù)出現(xiàn)動(dòng)態(tài)規(guī)劃中，同一子問(wèn)題可能被多次計(jì)算。計(jì)算效率低下重復(fù)計(jì)算會(huì)導(dǎo)致算法效率低下，尤其當(dāng)子問(wèn)題規(guī)模較大時(shí)。記憶化搜索動(dòng)態(tài)規(guī)劃通過(guò)存儲(chǔ)已計(jì)算過(guò)的子問(wèn)題結(jié)果，避免重復(fù)計(jì)算，提高效率。狀態(tài)轉(zhuǎn)移方程核心公式狀態(tài)轉(zhuǎn)移方程是動(dòng)態(tài)規(guī)劃的核心，它描述了不同狀態(tài)之間的關(guān)系，并定義了如何從較小的子問(wèn)題推導(dǎo)出較大的子問(wèn)題。遞歸定義狀態(tài)轉(zhuǎn)移方程通常以遞歸的形式定義，它將當(dāng)前狀態(tài)的值與先前狀態(tài)的值聯(lián)系起來(lái)。遞推關(guān)系動(dòng)態(tài)規(guī)劃算法通常利用狀態(tài)轉(zhuǎn)移方程來(lái)構(gòu)建一個(gè)遞推關(guān)系，并根據(jù)該關(guān)系逐步計(jì)算出最終結(jié)果。常見(jiàn)的動(dòng)態(tài)規(guī)劃問(wèn)題11.斐波那契數(shù)列動(dòng)態(tài)規(guī)劃可用于計(jì)算任何位置的斐波那契數(shù)。22.最長(zhǎng)公共子序列動(dòng)態(tài)規(guī)劃用于找到兩個(gè)字符串的最長(zhǎng)公共子序列。33.最長(zhǎng)遞增子序列動(dòng)態(tài)規(guī)劃用于找到給定序列的最長(zhǎng)遞增子序列。44.0-1背包問(wèn)題動(dòng)態(tài)規(guī)劃用于確定從給定物品集合中選擇的物品的最大價(jià)值，以滿足容量約束。斐波那契數(shù)列定義斐波那契數(shù)列是一個(gè)數(shù)學(xué)數(shù)列，其中每個(gè)數(shù)字都是前兩個(gè)數(shù)字的總和。遞歸公式斐波那契數(shù)列的遞歸公式為：F(n)=F(n-1)+F(n-2)，其中F(0)=0，F(xiàn)(1)=1。應(yīng)用斐波那契數(shù)列在計(jì)算機(jī)科學(xué)、數(shù)學(xué)和自然科學(xué)中都有廣泛的應(yīng)用。最長(zhǎng)公共子序列定義最長(zhǎng)公共子序列(LongestCommonSubsequence,LCS)問(wèn)題是指：給定兩個(gè)字符串，找到這兩個(gè)字符串中最長(zhǎng)的公共子序列。舉例例如，字符串"ACGT"和"AGGTAB"的最長(zhǎng)公共子序列是"AGT"，長(zhǎng)度為3。最長(zhǎng)遞增子序列子序列定義子序列是從原序列中選取任意個(gè)元素，保持順序不變。遞增子序列子序列元素按順序遞增，無(wú)需連續(xù)。最長(zhǎng)子序列在所有遞增子序列中，長(zhǎng)度最長(zhǎng)的子序列。0-1背包問(wèn)題11.問(wèn)題描述給定一個(gè)背包容量和一組物品，每個(gè)物品都有重量和價(jià)值，要求選擇物品放入背包，使得背包內(nèi)物品的總價(jià)值最大，且總重量不超過(guò)背包容量。22.關(guān)鍵限制每個(gè)物品只能選擇一次，即要么完全裝入背包，要么不裝入背包，不能將物品分割。33.解決方法動(dòng)態(tài)規(guī)劃方法可以有效解決0-1背包問(wèn)題，通過(guò)構(gòu)建狀態(tài)轉(zhuǎn)移方程，遍歷所有物品，并記錄每個(gè)狀態(tài)下的最大價(jià)值。44.應(yīng)用場(chǎng)景0-1背包問(wèn)題在資源分配、投資組合優(yōu)化、貨物運(yùn)輸?shù)阮I(lǐng)域有著廣泛的應(yīng)用。硬幣找零問(wèn)題問(wèn)題描述給定不同面值的硬幣和一個(gè)總金額，求解最少需要多少枚硬幣來(lái)湊成該總金額。動(dòng)態(tài)規(guī)劃解法使用動(dòng)態(tài)規(guī)劃，創(chuàng)建一個(gè)數(shù)組存儲(chǔ)不同金額的最小硬幣數(shù)量，通過(guò)狀態(tài)轉(zhuǎn)移方程計(jì)算每個(gè)金額所需的最小硬幣數(shù)量。應(yīng)用場(chǎng)景常見(jiàn)于自動(dòng)售貨機(jī)、銀行找零等場(chǎng)景，需要根據(jù)不同的金額組合提供最優(yōu)的硬幣數(shù)量方案。編輯距離問(wèn)題概念編輯距離是指兩個(gè)字符串之間，通過(guò)插入、刪除、替換操作，將一個(gè)字符串轉(zhuǎn)化為另一個(gè)字符串所需要的最少操作次數(shù)。應(yīng)用場(chǎng)景編輯距離廣泛應(yīng)用于自然語(yǔ)言處理、文本匹配、拼寫檢查、基因序列比對(duì)等領(lǐng)域。動(dòng)態(tài)規(guī)劃求解使用動(dòng)態(tài)規(guī)劃算法可以有效地計(jì)算兩個(gè)字符串的編輯距離，其時(shí)間復(fù)雜度為O(m*n)，其中m和n分別為兩個(gè)字符串的長(zhǎng)度。最小路徑和從左上角到右下角的最小路徑和。每次只能向下或向右移動(dòng)一步。動(dòng)態(tài)規(guī)劃解決此問(wèn)題，記錄每個(gè)位置到終點(diǎn)的最小路徑和。狀態(tài)轉(zhuǎn)移方程：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]股票買賣問(wèn)題股票價(jià)格波動(dòng)股票價(jià)格會(huì)在一段時(shí)間內(nèi)不斷變化。買入和賣出在合適的時(shí)間買入低價(jià)股票，并在價(jià)格上漲時(shí)賣出以獲取利潤(rùn)。最大利潤(rùn)動(dòng)態(tài)規(guī)劃可用于找到股票買賣交易的最大利潤(rùn)。動(dòng)態(tài)規(guī)劃通過(guò)記錄過(guò)去交易信息來(lái)優(yōu)化未來(lái)交易決策。爬樓梯問(wèn)題問(wèn)題描述一個(gè)人想要爬上n級(jí)臺(tái)階。每次可以爬1級(jí)或2級(jí)臺(tái)階。問(wèn)有多少種不同的爬樓梯方法？動(dòng)態(tài)規(guī)劃思路定義dp[i]表示爬到第i級(jí)臺(tái)階的方法數(shù)量。dp[i]可以由爬到第i-1級(jí)和第i-2級(jí)臺(tái)階的方案數(shù)累加得到。打家劫舍問(wèn)題問(wèn)題描述假設(shè)你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房屋都存放著特定金額的現(xiàn)金。你不能偷竊相鄰的房屋，因?yàn)樗鼈冇邪踩到y(tǒng)連接，會(huì)報(bào)警。動(dòng)態(tài)規(guī)劃解法使用動(dòng)態(tài)規(guī)劃，定義dp[i]表示偷竊前i間房屋的最大收益。狀態(tài)轉(zhuǎn)移方程dp[i]=max(dp[i-1],dp[i-2]+nums[i])，表示偷竊第i間房屋或不偷竊，兩種情況的收益最大值。矩陣路徑問(wèn)題問(wèn)題描述給定一個(gè)mxn的矩陣，每個(gè)單元格都有一個(gè)非負(fù)整數(shù)，從左上角開始，每次只能向下或向右移動(dòng)一步，到達(dá)右下角的最小路徑和是多少？動(dòng)態(tài)規(guī)劃解法定義dp[i][j]為從起點(diǎn)到(i,j)的最小路徑和，狀態(tài)轉(zhuǎn)移方程為dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]。邊界條件dp[0][0]=grid[0][0]，dp[i][0]=dp[i-1][0]+grid[i][0]，dp[0][j]=dp[0][j-1]+grid[0][j]。時(shí)間復(fù)雜度O(m*n)，空間復(fù)雜度可以優(yōu)化為O(n)，因?yàn)橹恍枰４嫔弦恍械臄?shù)據(jù)。子集生成問(wèn)題11.遞歸枚舉使用遞歸算法遍歷所有可能的子集組合。22.位運(yùn)算利用位運(yùn)算來(lái)表示子集的選取情況。33.回溯算法逐步構(gòu)建子集，并在不符合條件時(shí)回退。44.迭代方法使用循環(huán)迭代來(lái)生成所有可能的子集。最長(zhǎng)回文子串問(wèn)題回文串回文串是指正著讀和反著讀都一樣的字符串，例如"aba"、"racecar"。最長(zhǎng)子串給定一個(gè)字符串，找到其中最長(zhǎng)的回文子串。動(dòng)態(tài)規(guī)劃使用動(dòng)態(tài)規(guī)劃來(lái)記錄每個(gè)子串是否為回文串，并逐步構(gòu)建最長(zhǎng)回文子串。最大子數(shù)組和問(wèn)題描述給定一個(gè)整數(shù)數(shù)組，找到一個(gè)具有最大和的連續(xù)子數(shù)組（至少包含一個(gè)元素）。動(dòng)態(tài)規(guī)劃思路定義狀態(tài)dp[i]表示以第i個(gè)元素結(jié)尾的最大子數(shù)組和，通過(guò)狀態(tài)轉(zhuǎn)移方程dp[i]=max(dp[i-1]+nums[i],nums[i])進(jìn)行迭代計(jì)算。優(yōu)化可以使用一個(gè)變量記錄全局最大子數(shù)組和，并不斷更新。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。硬幣兌換問(wèn)題11.問(wèn)題描述給定一組面值的硬幣，求解用這些硬幣湊成目標(biāo)金額的最小硬幣數(shù)量。22.問(wèn)題分析可以采用動(dòng)態(tài)規(guī)劃的思想，將問(wèn)題分解成子問(wèn)題，并使用狀態(tài)轉(zhuǎn)移方程來(lái)進(jìn)行求解。33.狀態(tài)定義定義狀態(tài)dp[i]表示湊成金額i所需的最小硬幣數(shù)量。44.狀態(tài)轉(zhuǎn)移對(duì)于每個(gè)金額i，遍歷所有面值的硬幣，選擇能夠湊成金額i的最少硬幣數(shù)量。數(shù)字三角形問(wèn)題問(wèn)題描述給定一個(gè)數(shù)字三角形，求從頂點(diǎn)到最底層任意一點(diǎn)的路徑總和最大值，每次只能向下走或向右走。例如，一個(gè)數(shù)字三角形如下：7388102744從頂點(diǎn)7出發(fā)，可以走7->3->8->7->4，路徑總和為29，為最大值。動(dòng)態(tài)規(guī)劃解法使用二維數(shù)組dp[i][j]表示到達(dá)第i行第j列的路徑總和最大值。dp[i][j]可以從dp[i-1][j]或dp[i-1][j-1]轉(zhuǎn)移而來(lái)，狀態(tài)轉(zhuǎn)移方程為：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]。最后，返回dp[n-1][0]到dp[n-1][n-1]中的最大值，即為從頂點(diǎn)到最底層任意一點(diǎn)的路徑總和最大值。單詞拆分問(wèn)題動(dòng)態(tài)規(guī)劃思路將原字符串拆分成子串，判斷子串是否在詞典中。狀態(tài)轉(zhuǎn)移方程dp[i]表示字符串前i個(gè)字符能否拆分成詞典中的單詞。區(qū)域和檢索-數(shù)組不可變數(shù)組前綴和計(jì)算數(shù)組前綴和，將數(shù)組元素累加。查詢優(yōu)化使用前綴和數(shù)組，可以高效地查詢?nèi)我庾訑?shù)組的和。最小編輯距離定義編輯距離是指將一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串所需的最小操作次數(shù)。操作允許的操作包括插入、刪除和替換字符。應(yīng)