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

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