1、動態規劃2009級信科1班李遠韜動態規劃的基本原理 將問題轉化為規模更小的問題解決。 動態規劃與搜索的區別在于動態規劃會將已經解決過的子問題的解保存下來，下次需要時直接調用(以空間換時間)，而搜索則會將已經計算過的問題再計算一遍。狀態、階段與決策 狀態狀態：用于描述一個子問題 階段階段：按照一定的順序計算所有子問題 決策決策：通過決策將一個問題轉化為更小的子問題使用動態規劃的兩個基本條件 最優子結構最優子結構：問題的最優解只取決與子問題的最優解，即局部最優推出全局最優 無后效性無后效性：問題只依賴于更小的子問題，即能夠按一定的順序計算每個子問題，使得每個子問題的解都只依賴于前面已經計算過的問題

2、的解一個簡單的例子：最長上升子序列 給出一個序列a1,a2,an,找到序列a的子序列a(i1),a(i2),.,a(il)，1=i1i2.il=n，a(i1)a(i2).a(il),使得l最大一個簡單的例子：最長上升子序列 狀態：狀態：fi表示序列a1,a2,.,ai的包含ai的最長的子序列的長度 階段：階段：按i從小到大劃分階段，即按照i從小到大的順序計算fi，計算f(i)時只依賴于前面計算過的f值 決策：決策：枚舉f(i)對應的子序列a(i1),a(i2),.,a(i(l-1),i中i(l-1)的值，設i(l-1)=j,則問題轉化為在a1,a2,.,aj中找最長上升子序列一個簡單的例子：最

3、長上升子序列 狀態轉移方程：f(i)=maxf(j)+1,(1=ji,ajai) 時間復雜度：O(n2)動態規劃的兩種優化方法 簡化狀態，減少狀態總數 減少可行的決策牛場圍欄(fence) 有N種木料，長度分別為L1,L2,.,LN,每種木料數量無限，每根木料最多可以削短M米，且只能削去整數米，用這些木料修建圍欄，問無法修建的最大圍欄的長度，如果這個值為無窮大或者任何長度的圍欄都可以修建，輸出-1 數據范圍：N=100,M=3000,1=Li=3000簡化問題 預處理：將每根木料分別削去0,1,2,.,m，得到m根木料，再統計所有的木料長度，去除重復 問題簡化為有m根木料，長度分別為L1,L2

4、,.,Lm(不能削短)，問不能拼出的最長圍欄的長度（或輸出無解） 下面只討論簡化后的問題牛場圍欄(fence) 一個很自然的想法是通過動態規劃計算出對于每個長度L，能否通過現有的木料拼出，但是長度L是沒有限制的，即狀態的總數可以達到無限，必須減少狀態總數牛場圍欄(fence) 如果存在長度為L的木料，注意到如果可以拼出長度為x的圍欄，那么長度為x+L,x+2L,x+3L,.,x+kL.,的圍欄都可以被拼出牛場圍欄(fence) 我們將狀態設為f(i)，(0=iL)表示最小的整數x,滿足x可以被拼出，且x mod L=i，如果x不存在，則f(i)為正無窮 為了減少狀態總數，加快速度，我們取L=m

5、inL1,L2,.,Lm 如果我們能計算出所有的f(i),則答案ans=maxf(i)-L,ans0時則所有長度的圍欄都可以被拼出牛場圍欄(fence) 狀態轉移方程： f(i)=minf(j)+Lk ,(j+Lk) mod L=i) 如何劃分階段？ 如果按照i從小到大劃分階段，不滿足無后效性牛場圍欄(fence) 仔細觀察狀態轉移方程 f(i)=minf(j)+Lk ,(j+Lk) mod L=i) 注意到f(0)=0,我們建立一個N個節點的圖，以0為源點，對所有滿足(j+Lk) mod L=i的點i,j，從i向j連一條長度為Lk的邊，則f(i)就等于從0到i的最短路 時間復雜度：O(L2)

6、牛場圍欄(fence) 此題中的最短路算法本質上也可以看做是以f(i)的值從小到大劃分階段的動態規劃，因為f(i)只能由比f(i)的值小的狀態f(j)推出。小結 在上面一道題中，我們通過分析問題，減少狀態總數，成功的解決了此題 下面我們來看一個通過減少決策總數來優化動態規劃的例子序列劃分 給出一個正整數序列，a1,a2,aN，將序列分成若干段，每段有一個權值，如將ai,aj劃分成一段，則該段權值F=(a(i)+a(i+1)+a(j)*i+T，求一種劃分方案，使得每段的權值之和最小 數據范圍：數據范圍：1=N=1000000序列劃分 我們可以很容易的得到一個O(N2)的動態規劃 設狀態為fi,表

7、示序列a1,a2,ai的最優劃分方案中每段的權值之和 狀態轉移方程為fi=min(sumi-sumk)*i+t+fk,其中sumi=a1+a2+ai 但是此題中N的范圍可以達到1000000，需要優化算法序列劃分 對于狀態fi的兩種決策k1,k2(k1k2)，我們來分析一下決策k1優于k2的條件 決策k1優于k2等價于 (sumi-sumk1)*i+T+fk1(sumi-sumk2)*i+T+fk2 將上式變形后得 i(fk2-fk1)/(sumk2-sumk1)序列劃分 我們設g(k1,k2)=(fk2-fk1)/(sumk2-sumk1),(k1i序列劃分 對于任意三個決策k1k2g(k2

8、,k3) 情況一：如果g(k2,k3)i，則有g(k1,k2)i，決策k1優于決策k2 所以決策k2無論如何都不可能成為最優決策序列劃分 對于任意兩個決策k1,k2(k1k2),由于我們按照i值從小到大計算fi，如果g(k1,k2)i，有g(k1,k2)j，即k1在以后的計算中也不可能成為最優決策序列劃分 我們用一個隊列k來維護所有可能成為最優決策的決策 k1k2k3kn，那么k1,k2,kn應該滿足：ig(k1,k2)g(k2,k3)g(kn,k)，則kn為無用決策，將kn從隊列中刪除，如此反復直到滿足g(kn-1,kn)g(kn,k)，將k插入隊列尾部 （2）刪除決策：如果g(k1,k2)i，