【正文】 (i1,j)，從而 Size(i,j)=Size(i1,j)。 (1)當 i=1時， (2)當 i1時， jπ(i)。 N(i,j)的最大不相交子集為 MNS(i,j)。換句話說，該問題要求確定導線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。對于任何 1≤ij≤n，第 i條連線和第 j條連線相交的充分且必要的條件是 π(i)π(j)。其中 π(i)是 {1,2,…,n} 的一個排列。 32 電路布線 在一塊電路板的上、下 2端分別有 n個接線柱。由最優(yōu)子結構性質易知： 其中 11)},1m a x (b*][{m i n][ }2 5 6,m i n {1 ?????? ?? ikikkisis ik?????? ?????? ?? ?? 1}{m a xl o g),b m a x ( kjki pji算法復雜度分析： 由于算法 press中對 k的循環(huán)次數(shù)不超這 256，故對每一個確定的 i，可在時間 O(1)內完成的計算。即圖象壓縮問題滿足最優(yōu)子結構性質。 ???? 11][][ ikklit },{ ][][1][ ilititi ppS ??? ??????? ?????? ?? ???? 1m a xlo g ][][1][ kilitkiti phmibilmi11][*][1???31 圖像壓縮 設 l[i]， b[i] (1≤i≤ m )，是 {p1,p2,…,pn} 的最優(yōu)分段。 圖象壓縮問題要求確定象素序列 {p1,p2,… ,pn}的最優(yōu)分段，使得依此分段所需的存儲空間最少。因此，第 i個象素段所需的存儲空間為 l[i]*b[i]+11位。設 則第 i個象素段 Si為 設 ，則 hi?b[i]?8。 30 圖像壓縮 圖象的變位壓縮存儲格式將所給的象素點序列{p1,p2,…,p n},0≤pi≤255分割成 m個連續(xù)段 S1,S2,…,S m。*39。+39。 m2是 p(i+s，js)的任意一種合并方式得到的值，而 c和 d分別是在所有可能的合并中得到的最小值和最大值。 ?如果這條鏈的最后一次合并運算在 op[i+s]處發(fā)生 (1≤s≤j1)，則可在 op[i+s]處將鏈分割為 2個子鏈 p(i， s)和 p(i+s， js)。 問題 :對于給定的多邊形，計算最高得分。 最后，所有邊都被刪除，游戲結束。 隨后 n1步按以下方式操作： (1)選擇一條邊 E以及由 E連接著的 2個頂點 V1和 V2； (2)用一個新的頂點取代邊 E以及由 E連接著的 2個頂點 V1和 V2。所有邊依次用整數(shù)從 1到 n編號。由此， t[i][j]可遞歸地定義為： ??????????? ??? jijivvvwjktkitjit jkijki)}(]][1[]][[{m i n0]][[128 多邊形游戲 多邊形游戲是一個單人玩的游戲，開始時有一個由 n個頂點構成的多邊形。由最優(yōu)子結構性質， t[i][j]的值應為t[i][k]的值加上 t[k+1][j]的值，再加上三角形 vi1vkvj的權值，其中i≤k≤j1。 ?t[i][j]的值可以利用最優(yōu)子結構性質遞歸地計算。為方便起見，設退化的多邊形{vi1,vi}具有權值 0。因為若有 {v0,v1,…,v k}或{vk,vk+1,…,v n}的更小權的三角剖分將導致 T不是最優(yōu)三角剖分的矛盾。 ?事實上，若凸 (n+1)邊形 P={v0,v1,…,v n1}的最優(yōu)三角剖分 T包含三角形 v0vkvn， 1≤k≤n1，則 T的權為 3個部分權的和：三角形 v0vkvn的權，子多邊形 {v0,v1,…,v k}和 {vk,vk+1,…,v n}的權之和。三角剖分中的一條弦 vivj， ij，對應于矩陣連乘積A[i+1:j]。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語法樹表示。例如，完全加括號的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應的語法樹如圖 (a)所示。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權之和為最小。 ?多邊形的三角剖分 是將多邊形分割成互不相交的三角形的弦的集合 T。 ?若 vi與 vj是多邊形上不相鄰的 2個頂點，則線段 vivj稱為多邊形的一條弦。進一步的分析還可將空間需求減至 O(min(m,n))。事實上，在計算 c[i][j]時，只用到數(shù)組 c的第 i行和第 i1行。對于給定的數(shù)組元素 c[i][j]，可以不借助于數(shù)組 b而僅借助于 c本身在時間內確定 c[i][j]的值是由 c[i1][j1]， c[i1][j]和 c[i][j1]中哪一個值所確定的。 } 23 算法的改進 ?在算法 lcsLength和 lcs中，可進一步將數(shù)組 b省去。 } else if (b[i][j]== 2) LCS(i1， j， x， b)。 if (b[i][j]== 1){ LCS(i1， j1， x， b)。 b[i][j]=3。 b[i][j]=2。 b[i][j]=1。 j = n。 i = m。 i++) c[0][i] = 0。 for (i = 1。 i = m。 void LCSLength(int m， int n， char *x，char *y， int **c， int **b) { int i， j。0,。故此時 C[i][j]=0。其中， Xi={x1,x2,…,x i}； Yj={y1,y2,…,y j}。 21 子問題的遞歸結構 由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。 由此可見， 2個序列的最長公共子序列包含了這 2個序列的前綴的最長公共子序列。 (2)若 xm≠yn且 zk≠xm，則 Z是 xm1和 Y的最長公共子序列。 ?給定 2個序列 X={x1,x2,… ,xm}和 Y={y1,y2,… ,yn}，找出 X和 Y的最長公共子序列。例如，序列 Z={B， C， D， B}是序列 X={A， B， C， B，D， A， B}的子序列，相應的遞增下標序列為 {2， 3， 5，7}。 return u。 s[i][j] = k。 k++) { int t = LookupChain(i， k) + LookupChain(k+1， j) + p[i1]*p[k]*p[j]。 for (int k = i+1。 int u = LookupChain(i， i) + LookupChain(i+1， j) + p[i1]*p[i]*p[j]。 int LookupChain(int i， int j) { if (m[i][j] 0) return m[i][j]。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。 ?動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結果。 同一個問題可以有多種 方式刻劃 它 的最優(yōu)子結構，有些表示方法的求解速度更快（空間占用小，問題的維度低） 17 動態(tài)規(guī)劃算法的基本要素 二、重疊子問題 ?遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。 ?利用問題的最優(yōu)子結構性質，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構造出整個問題的最優(yōu)解。這種性質稱為 最優(yōu)子結構性質 。算法所占用的空間顯然為 O(n2)。循環(huán)體內的計算量為 O(1)，而 3重循環(huán)的總次數(shù)為 O(n3)。 s[i][j] = k。 k++) { int t = m[i][k] + m[k+1][j] + p[i1]*p[k]*p[j]。 for (int k = i+1。 m[i][j] = m[i+1][j]+ p[i1]*p[i]*p[j]。 i = n r+1。 r = n。 i++) m[i][i] = 0。每個子問題只計算一次，