動態(tài)規(guī)劃算法策略LET'SEMBARKONTODAY'SSHARINGJOURNEYTOGETHER01動態(tài)規(guī)劃思想Let'sembarkontoday'sjourneyofsharingandcommunicationtogether動態(tài)規(guī)劃算法是一種解決最優(yōu)化問題的有效方法，其基本思想是將待求解問題分解成若干子問題，先求解子問題，再結(jié)合這些子問題的解得到原問題的解。與分治法不同的是，適合用動態(tài)規(guī)劃法求解的問題經(jīng)分解得到的子問題往往不是互相獨立的。例如在矩陣連乘問題中，不同的計算次序會導致不同的計算量，而動態(tài)規(guī)劃可以找到最優(yōu)的計算次序。通常按四個步驟設計動態(tài)規(guī)劃算法。首先，找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；其次，遞歸地定義最優(yōu)值；然后，以自底向上的方式計算最優(yōu)值；最后，根據(jù)計算最優(yōu)值時得到的信息構(gòu)造最優(yōu)解。在只需要求出最優(yōu)值的情形下，最后一步可以省略。例如在矩陣連乘問題中，通過這四個步驟可以找到最優(yōu)的計算次序。動態(tài)規(guī)劃算法有兩個基本要素，即最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)指問題的最優(yōu)解包含著其子問題的最優(yōu)解，如矩陣連乘問題中，計算整體的最優(yōu)次序包含了子鏈的最優(yōu)次序。重疊子問題性質(zhì)是指在用遞歸算法自頂向下解問題時，有些子問題會被重復計算，而動態(tài)規(guī)劃通過保存已解決的子問題的答案來避免重復計算，提高效率?；疽貙W習要點設計步驟概念理解動態(tài)規(guī)劃將復雜的問題分解為多個子問題，這些子問題之間可能存在關(guān)聯(lián)。例如在矩陣連乘問題中，將矩陣鏈分解為不同的子鏈，通過求解子鏈的最優(yōu)計算次序來得到整個矩陣鏈的最優(yōu)計算次序。這種分解方式可以將大問題轉(zhuǎn)化為小問題，便于求解。算法思想求解原問題由于子問題可能會被重復計算，動態(tài)規(guī)劃采用一個表來記錄所有已解決的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這樣在需要用到某個子問題的答案時，直接從表中查找，避免了大量的重復計算，從而提高了算法的效率。避免重復在解決了所有子問題并記錄下答案后，通過結(jié)合這些子問題的解來得到原問題的解。在矩陣連乘問題中，根據(jù)子鏈的最優(yōu)計算次序和記錄的信息，構(gòu)造出整個矩陣鏈的最優(yōu)計算次序。這種從子問題到原問題的求解過程體現(xiàn)了動態(tài)規(guī)劃的核心思想。問題分解找出最優(yōu)解的性質(zhì)設計動態(tài)規(guī)劃算法的第一步是找出最優(yōu)解的性質(zhì)。以矩陣連乘為例，需要分析不同加括號方式對計算量的影響，從而確定最優(yōu)解的結(jié)構(gòu)特征。遞歸定義最優(yōu)值第二步是遞歸定義最優(yōu)值。通過建立子問題的遞歸關(guān)系，定義最優(yōu)值的計算公式。例如，在矩陣連乘中，最優(yōu)值可以通過遞歸公式計算出最小乘法次數(shù)。自底向上計算最優(yōu)值第三步是自底向上計算最優(yōu)值。通過表格記錄子問題的解，從最小的子問題開始逐步計算，最終得到全局最優(yōu)解。這種方法避免了遞歸中的重復計算。構(gòu)造最優(yōu)解最后一步是構(gòu)造最優(yōu)解。在需要具體解時，根據(jù)表格記錄的信息，逐步構(gòu)造出最優(yōu)解。例如，在矩陣連乘中，可以通過回溯表格得到最優(yōu)加括號方式。設計動態(tài)規(guī)劃算法的步驟具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問題也適合用動態(tài)規(guī)劃求解。最優(yōu)子結(jié)構(gòu)性質(zhì)意味著問題的最優(yōu)解包含了子問題的最優(yōu)解，如在矩陣連乘問題中，整體的最優(yōu)計算次序包含了子鏈的最優(yōu)計算次序。動態(tài)規(guī)劃利用這種性質(zhì)，通過求解子問題的最優(yōu)解來得到原問題的最優(yōu)解。動態(tài)規(guī)劃適用于解最優(yōu)化問題，如矩陣連乘的最優(yōu)計算次序、最長公共子序列、最大子段和等問題。這些問題都需要在多個可能的解中找到最優(yōu)解，而動態(tài)規(guī)劃通過其獨特的算法思想和步驟，可以高效地解決這類問題。子問題重疊最優(yōu)化問題當問題經(jīng)分解得到的子問題存在重疊時，動態(tài)規(guī)劃可以發(fā)揮其優(yōu)勢。在矩陣連乘問題中，不同的子鏈可能會有相同的子子鏈，這些子子鏈就是重疊的子問題。動態(tài)規(guī)劃通過記錄子問題的答案，避免了對這些重疊子問題的重復計算，提高了算法的效率。最優(yōu)子結(jié)構(gòu)適用場景02矩陣連乘問題Let'sembarkontoday'sjourneyofsharingandcommunicationtogether問題定義與計算量差異矩陣連乘問題定義矩陣連乘問題的目標是給定一系列矩陣，找到一種最優(yōu)的加括號方式，使得計算矩陣連乘積所需的數(shù)乘次數(shù)最少。矩陣乘法滿足結(jié)合律，不同的加括號方式會導致不同的計算量。計算量的顯著差異例如，對于三個矩陣A1、A2和A3，其維度分別為10×100、100×5和5×50。按((A1A2)A3)計算需要7500次乘法，而按(A1(A2A3))計算則需要75000次乘法，計算量相差10倍。窮舉搜索法通過列舉所有可能的加括號方式來尋找最優(yōu)解，但這種方法的計算量極大。對于n個矩陣的連乘積，不同的加括號方式數(shù)呈指數(shù)增長，使得窮舉法在實際應用中不可行。窮舉搜索法的局限性矩陣連乘積的加括號方式數(shù)可以用Catalan數(shù)來表示，即P(n)=C(n?1)。隨著n的增加，Catalan數(shù)呈指數(shù)增長，導致窮舉搜索法的計算量迅速變得無法承受。Catalan數(shù)與組合爆炸由于窮舉搜索法的計算量過大，我們需要尋找一種更高效的算法。動態(tài)規(guī)劃算法通過保存子問題的解，避免了重復計算，從而將指數(shù)級的計算量降低到多項式級別。動態(tài)規(guī)劃的必要性03020401根據(jù)計算m[i][j]的遞歸式，用動態(tài)規(guī)劃算法以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案，避免大量的重復計算。算法MatrixChain首先計算出m[i][i]=0（i=1,2,…,n），再按矩陣鏈長遞增的方式依次計算m[i][i+1]、m[i][i+2]等。該算法的計算時間上界為O(n3)，占用空間為O(n2)。建立遞歸關(guān)系分析最優(yōu)解結(jié)構(gòu)設計算A[i:j]的最少數(shù)乘次數(shù)為m[i][j]，原問題最優(yōu)值是m[1][n]。i=j時，A[i:j]為單一矩陣，無需計算，m[i][i]=0；i<j時，根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，m[i][j]遞歸定義為m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj，k是使計算量最小的斷開位置，用s[i][j]記錄對應m[i][j]的斷開位置k。構(gòu)造最優(yōu)解算法MatrixChain只是計算出了最優(yōu)值，并未給出最優(yōu)解。通過s[i][j]記錄的信息，可以構(gòu)造出問題的最優(yōu)解。s[i][j]中的數(shù)表明，計算矩陣鏈A[i:j]的最佳方式是在矩陣Ak和Ak+1之間斷開。從s[1][n]記錄的信息開始，逐步遞推，可以確定A[1:n]的最優(yōu)完全加括號方式。算法Traceback可以按此方式輸出計算A[i:j]的最優(yōu)計算次序。動態(tài)規(guī)劃求解設計矩陣連乘積最優(yōu)計算次序問題的動態(tài)規(guī)劃算法，需先分析最優(yōu)解結(jié)構(gòu)特征。將矩陣連乘積AiAi+1…Aj簡記為A[i:j]，考察A[1:n]的最優(yōu)計算次序。若該次序在Ak與Ak+1間斷開，完全加括號方式為((A1…Ak)(Ak+1…An))，且A[1:n]最優(yōu)次序中A[1:k]和A[k+1:n]的計算次序也最優(yōu)，體現(xiàn)了最優(yōu)子結(jié)構(gòu)性質(zhì)。計算最優(yōu)值算法分析空間復雜度算法MatrixChain占用的空間顯然為O(n2)，主要用于存儲m[i][j]和s[i][j]數(shù)組。在計算過程中，這些數(shù)組記錄了子問題的最優(yōu)值和斷開位置信息，為構(gòu)造最優(yōu)解提供了依據(jù)。雖然空間復雜度較高，但在可接受的范圍內(nèi)，且能有效解決矩陣連乘的最優(yōu)計算次序問題。矩陣連乘問題的動態(tài)規(guī)劃算法MatrixChain的主要計算量取決于程序中對r、i和k的三重循環(huán)。循環(huán)體內(nèi)的計算量為O(1)，而三重循環(huán)的總次數(shù)為O(n3)，因此該算法的計算時間上界為O(n3)。相比之下，窮舉搜索法的計算量隨n呈指數(shù)增長，動態(tài)規(guī)劃算法的效率更高。動態(tài)規(guī)劃算法比窮舉搜索法更有效，它充分利用了子問題重疊性質(zhì)，避免了大量的重復計算。對于n個矩陣的連乘積，窮舉搜索法需要列舉出所有可能的計算次序，計算量太大；而動態(tài)規(guī)劃算法通過保存已解決的子問題的答案，只對每個子問題計算一次，從而提高了算法的效率。時間復雜度算法優(yōu)勢020103計算過程展示以計算矩陣連乘積A1A2A3A4A5A6為例，設各矩陣的維數(shù)分別為A1:30×35，A2:35×15，A3:15×5，A4:5×10，A5:10×20，A6:20×25。根據(jù)這些維數(shù)，利用動態(tài)規(guī)劃算法MatrixChain計算m[i][j]和s[i][j]的值，以確定最優(yōu)的計算次序。最優(yōu)解輸出在計算m[i][j]時，依遞歸式進行計算。例如，在計算m[2][5]時，根據(jù)遞歸式和已知條件，可得到相應的值和斷開位置k。算法按矩陣鏈長遞增的方式依次計算各個m[i][j]的值，最終得到整個矩陣鏈的最優(yōu)計算次序。實例演示矩陣維數(shù)設定通過算法Traceback，根據(jù)MatrixChain計算出的s[i][j]信息，可以輸出計算A[1:6]的最優(yōu)計算次序。在這個例子中，輸出的最優(yōu)計算次序為((A1(A2A3))((A4A5)A6))，這表明了動態(tài)規(guī)劃算法在實際問題中的有效性。03算法要素分析Let'sembarkontoday'sjourneyofsharingandcommunicationtogether010203證明方法當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。在矩陣連乘問題中，計算矩陣鏈的最優(yōu)次序包含了子鏈的最優(yōu)次序；在最長公共子序列問題中，兩個序列的最長公共子序列包含了這兩個序列的前綴的最長公共子序列。這種性質(zhì)為動態(tài)規(guī)劃算法的設計提供了重要線索。應用意義最優(yōu)子結(jié)構(gòu)性質(zhì)是動態(tài)規(guī)劃算法求解問題的關(guān)鍵特征。利用該性質(zhì)，動態(tài)規(guī)劃算法可以以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。在設計動態(tài)規(guī)劃算法時，首先要分析問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這有助于確定算法的可行性和設計思路。定義與特征最優(yōu)子結(jié)構(gòu)通常采用反證法來證明問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。在矩陣連乘問題中，假設計算A[1:k]的次序不是最優(yōu)的，用更優(yōu)的次序替換原來的次序，會得到比最優(yōu)次序所需計算量更少的計算A[1:n]的計算量，這與A[1:n]的最優(yōu)次序矛盾，從而證明了計算A[1:k]的次序也是最優(yōu)的。030201算法利用以計算矩陣連乘積最優(yōu)計算次序為例，直接遞歸算法RecurMatrixChain的計算時間隨n指數(shù)增長，而動態(tài)規(guī)劃算法MatrixChain只需計算時間O(n3)。這是因為直接遞歸算法會重復計算許多子問題，而動態(tài)規(guī)劃算法充分利用了子問題重疊性質(zhì)，對每個不同的子問題只計算一次，從而節(jié)省了大量不必要的計算?？捎脛討B(tài)規(guī)劃算法求解的問題應具備子問題的重疊性質(zhì)。在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被反復計算。在計算矩陣連乘積最優(yōu)計算次序時，利用遞歸式直接計算A[i:j]，許多子問題會被重復計算，這就是子問題重疊的體現(xiàn)。概念解釋動態(tài)規(guī)劃算法正是利用了子問題的重疊性質(zhì)，對每個子問題只解一次，然后將其解保存在一個表格中。當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。在矩陣連乘問題中，動態(tài)規(guī)劃算法MatrixChain通過保存已解決的子問題答案，避免了大量的重復計算，提高了算法的效率。效率對比重疊子問題算法實現(xiàn)算法MemoizedMatrixChain首先將數(shù)組m初始化為0，表示相應的子問題還未被計算。在調(diào)用LookupChain()時，若m[i][j]>0，則表示其中存儲的是所要求子問題的計算結(jié)果，直接返回此結(jié)果即可；否則與直接遞歸算法一樣，自頂向下遞歸計算，并將計算結(jié)果存入m[i][j]后返回。備忘錄方法備忘錄算法MemoizedMatrixChain耗時O(n3)。共有O(n2)個備忘記錄項m[i][j]，這些記錄項的初始化耗費O(n2)時間，每個記錄項只填入一次，每次填入時耗費O(n)時間。通過使用備忘錄技術(shù)，直接遞歸算法的計算時間從Ω(2n)降至O(n3)，提高了算法的效率。方法原理備忘錄方法是動態(tài)規(guī)劃算法的變形，它用表格保存已解決的子問題的答案，在下次需要解此子問題時，只要簡單地查看該子問題的解答，而不必重新計算。與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的。在解矩陣連乘積最優(yōu)計算次序問題時，備忘錄算法MemoizedMatrixChain用數(shù)組m來記錄子問題的最優(yōu)值。效率分析最優(yōu)子結(jié)構(gòu)與重疊子問題動態(tài)規(guī)劃算法的兩大基本要素是：最優(yōu)子結(jié)構(gòu)和重疊子問題。最優(yōu)子結(jié)構(gòu)保證了問題的最優(yōu)解可以通過子問題的最優(yōu)解構(gòu)造；重疊子問題則使得動態(tài)規(guī)劃算法可以通過保存子問題的解來避免重復計算。01在判斷一個問題是否適合使用動態(tài)規(guī)劃算法時，需要檢查該問題是否具有最優(yōu)子結(jié)構(gòu)和重疊子問題。如果滿足這兩個條件，那么動態(tài)規(guī)劃算法通常是解決該問題的有效方法。

02要素的應用與判斷兩大基本要素備忘錄方法對比備忘錄方法的特點備忘錄方法是一種自頂向下的動態(tài)規(guī)劃算法。它通過保存已解決子問題的答案，避免了重復計算。與自底向上的動態(tài)規(guī)劃算法相比，備忘錄方法的控制結(jié)構(gòu)更接近于直接遞歸算法。備忘錄方法與動態(tài)規(guī)劃算法的比較備忘錄方法和動態(tài)規(guī)劃算法的時間復雜度都是O(n^3)，但在某些情況下，備忘錄方法可能更高效。當子問題空間中的部分子問題不需要求解時，備忘錄方法可以節(jié)省計算量。算法的實現(xiàn)MemoizedMatrixChain算法通過一個二維數(shù)組m來保存子問題的最優(yōu)值。在計算過程中，如果某個子問題已經(jīng)計算過，則直接返回其結(jié)果；否則，遞歸地計算該子問題的最優(yōu)值，并將其保存在m中。010203適用場景選擇最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)是動態(tài)規(guī)劃算法的核心要素。最優(yōu)子結(jié)構(gòu)性質(zhì)為算法提供了從子問題的最優(yōu)解構(gòu)造原問題最優(yōu)解的依據(jù)，而重疊子問題性質(zhì)使得算法可以避免重復計算，提高效率。備忘錄方法則是對動態(tài)規(guī)劃算法的優(yōu)化，進一步提高了算法的性能。核心要素作用當一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃算法比用備忘錄方法好，因為動態(tài)規(guī)劃算法沒有任何多余的計算。當子問題空間中的部分子問題可不必求解時，用備忘錄方法較有利，因為它只解那些確實需要求解的子問題。要素總結(jié)在設計動態(tài)規(guī)劃算法時，首先要分析問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)。如果具備這些性質(zhì)，則可以考慮使用動態(tài)規(guī)劃算法或備忘錄方法來解決問題。同時，根據(jù)問題的具體特點和要求，選擇合適的算法實現(xiàn)方式，以達到最佳的求解效果。算法設計指導04其它應用Let'sembarkontoday'sjourneyofsharingandcommunicationtogether04010302算法Compress只需O(n)空間，由于算法中j的循環(huán)次數(shù)不超過256，故對每個確定的i，可在O(1)時間內(nèi)完成計算，整個算法所需的計算時間為O(n)。問題背景在計算機中常用像素點灰度值序列{p1,p2,…,pn}表示圖像，圖像的變位壓縮存儲格式將像素點序列分割成m個連續(xù)段S1,S2,…,Sm。第i個像素段Si中有l(wèi)[i]個像素，且該段中每個像素都只用b[i]位表示。圖像壓縮問題要求確定像素序列的最優(yōu)分段，使得依此分段所需的存儲空間最小。圖像壓縮問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設l[i]和b[i]是像素序列的一個最優(yōu)分段，則l[1]、b[1]是{p1,…,pl[1]}的一個最優(yōu)分段，且l[i]和b[i]（2≤i≤m）是{pl[1]+1,…,pn}的一個最優(yōu)分段。遞歸計算與構(gòu)造復雜度分析設s[i]是像素序列{p1,p2,…,pi}的最優(yōu)分段所需的存儲位數(shù)，可據(jù)此設計解圖像壓縮問題的動態(tài)規(guī)劃算法Compress。算法Compress通過遞歸計算確定最優(yōu)分段所需的信息，用l[i]和b[i]記錄這些信息。由算法計算出的l和b可在O(n)時間內(nèi)構(gòu)造出相應的最優(yōu)解，算法Traceback可實現(xiàn)這一構(gòu)造過程。圖像壓縮最優(yōu)子結(jié)構(gòu)性質(zhì)一塊電路板的上、下兩端分別有n個接線柱，要求用導線(i,π(i))將上端接線柱i與下端接線柱π(i)相連。電路布線問題就是要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線，即確定導線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。算法MNS需要O(n2)計算時間和O(n2)空間，Traceback需要O(n)計算時間。通過動態(tài)規(guī)劃算法，可以有效地解決電路布線問題，確定最大不相交子集。最優(yōu)子結(jié)構(gòu)性質(zhì)解電路布線問題的動態(tài)規(guī)劃算法MNS根據(jù)問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以二維數(shù)組單元size[i][j]表示函數(shù)Size(i,j)的值。算法MNS耗時O(n2)，需要O(n2)空間。根據(jù)算法MNS計算出的size[i][j]值，算法Traceback可構(gòu)造出最優(yōu)解MNS(n,n)，計算時間為O(n)。電路布線問題描述計算與構(gòu)造復雜度總結(jié)電路布線問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。記N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}，N(i,j)的最大不相交子集為MNS(i,j)。當i=1時，可確定Size(1,j)的值；當i>1時，根據(jù)j與π(i)的大小關(guān)系，可確定Size(i,j)與Size(i-1,j)的關(guān)系。030104020-1背包問題最優(yōu)子結(jié)構(gòu)性質(zhì)0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(y1,y2,…,yn)是問題的一個最優(yōu)解，則(y2,y3,…,yn)是相應子問題的一個最優(yōu)解。通過反證法可以證明這一性質(zhì)，若(y2,y3,…,yn)不是子問題的最優(yōu)解，會得到比(y1,y2,…,yn)更優(yōu)的解，這與(y1,y2,…,yn)是最優(yōu)解矛盾。0-1背包問題給定n種物品和一背包，物品i的重量是wi，其價值為vi，背包的容量為c。在選擇裝入背包的物品時，對每種物品i只有裝入或不裝入兩種選擇，不能將物品i裝入背包多次，也不能只裝入部分的物品i。問題是找出一個n元0-1向量(x1,x2,…,xn)，使得裝入背包中物品的總價值最大。設所給0-1背包問題的子問題的最優(yōu)值為m(i,j)，可建立計算m(i,j)的遞歸式。當wi為正整數(shù)時，用二維數(shù)組m[][]來存儲m(i,j)的相應值，可設計解0-1背包問題的動態(tài)規(guī)劃算法Knapsack。算法Knapsack計算后，m[1][c]給出問題的最優(yōu)值，算法Traceback可構(gòu)造出相應的最優(yōu)解。問題描述遞歸關(guān)系與算法算法Knap