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

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