【正文】 o y2 do // 遞推中國象棋馬的列位置 for i←1 to n do // 遞推中國象棋馬在 j列的行位置 for k←1 to 4 do // 遞推中國象棋馬在（ i， j）的 4個跳動方向 begin 中國象棋馬由（ i， j）出發(fā)，沿著 k方向跳至（ x， y） if (x? ｛１ ..n｝ )∧ (y? {1..y2}) //計算狀態(tài)轉(zhuǎn)移方程 then map[x， y] ←map[i ， j]+map[x， y] end； //for writeln(map[x2， y2]： 0： 0)； //輸出從（ x1， y1）到（ x2， y2）的路徑數(shù)目 【 例題 2】 砝碼稱重 【 問題描述 】 設(shè)有 1g， 2g， 3g， 5g， 10g， 20g的砝碼各若干枚（其總重 ≤1000g），要求： 【 輸入格式 】 a1 a2 a3 a4 a5 a6(表示 1g砝碼有 a1個， 2g砝碼有 a2個， ....20g砝碼有 a6個 ) 【 輸出格式 】 Total=N (N表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不用的情況 ) 【 輸入樣例 】 1 1 0 0 0 0 【 輸出樣例 】 Total=3，表示可以稱出 1g， 2g， 3g三種不同的重量 【 算法分析 】 const num： array[1..6] of shortint=(1， 2， 3， 5， 10， 20)； //砝碼的重量序列 var a： array[1..6] of integer； //6種砝碼的個數(shù)｝ h： array[0..1000] of boolean； //重量的訪問標(biāo)志序列｝ n： array[0..1000] of integer； //n[0]—不同重量數(shù)； n[j]—第 j種重量 (１ ≤j≤n[0]) total， i， j， k： integer； //total—目前稱出的重量 我們按照第１種砝碼，第２種砝碼 …… 第６種砝碼的順序分析。在分析第 i種砝碼的放置方案時，依次在現(xiàn)有的不同重量的基礎(chǔ)上，放 1塊、 2塊 ……a[i] 塊，產(chǎn)生新的不同重量。 n[n[0]+1]=total│total=n[j]+k*num[i]， h[total]=false， 1≤i≤6， 1≤j≤n[0]， 1≤k≤a[i] 階段 i： 分析第 i種砝碼 (１ ≤i≤6)； 狀態(tài) j：枚舉現(xiàn)有的不同重量（１ ≤j≤n[0]）； 決策 k：在現(xiàn)有重量的基礎(chǔ)上放 k塊第 i種砝碼，產(chǎn)生重量 n[j]+k*num[i](１ ≤k≤a[i])； 計算過程如下： fillchar(h,sizeof(h),false)。 for i:=1 to 6 do read(a[i])。 //輸入６種砝碼的個數(shù) n[0]:=1。n[1]:=0。 //產(chǎn)生第１種重量０ for i:=1 to 6 do //階段：分析第 i種砝碼 for j:=1 to n[0] do //狀態(tài)：枚舉現(xiàn)有的不同重量 for k:=1 to a[i] do //決策：在現(xiàn)有重量的基礎(chǔ)上放 k塊第 i種砝碼｝ begin total:=n[j]+k*num[i]。 //產(chǎn)生重量 if not h[total] then //若該重量未產(chǎn)生過，則設(shè)訪問標(biāo)志 begin h[total]:=true。 inc(n[0])。 //重量進(jìn)入 n序列 n[n[0]]:=total。 end。 end。 writeln(‘Total=’,n[0]1)。 //輸出不同重量的個數(shù) 【 例題 3】 裝箱問題 【 問題描述 】 有一個箱子容量為 v（正整數(shù)， 0≤v≤20210），同時有 n個物品（ 0n≤30），每個物品有一個體積（正整數(shù)）。 要求從 n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。 【 輸入格式 】 箱子的容量 v 物品數(shù) n 接下來 n行，分別表示這 n個物品的體積 【 輸出格式 】 箱子剩余空間 【 輸入輸出樣例 】 輸入： 24 6 8 3 12 7 9 7 輸出： 0 【 算法分析 】 使用 動態(tài)程序設(shè)計方法計算箱子的最小剩余空間，如果按照物品序號依次考慮裝箱順序的話，則問題具有明顯的階段特征。問題是當(dāng)前階段的剩余空間最小，并不意味下一階段的剩余空間也一定最小，即該問題并不具備最優(yōu)子結(jié)構(gòu)的特征。但如果將裝箱的體積作為狀態(tài)的話，則階段間的狀態(tài)轉(zhuǎn)移關(guān)系順其自然，可使得最優(yōu)化問題變?yōu)榕卸ㄐ詥栴}。設(shè)狀態(tài)轉(zhuǎn)移方程 f[i， j]——在前 i個物品中選擇若干個物品（必須包括物品 i）裝箱，其體積正好為 j的標(biāo)志。顯然 f[i， j]=f[i1， jbox[i]]，即物品 i裝入箱子后的體積正好為 j的前提是 f[i1， jbox[i]]=true。初始時， f[0， 0]=true（ 1≤i≤n，box[i]≤j≤v）。 由 f[i， j]=f[i1， jbox[i]]可以看出，當(dāng)前階段的狀態(tài)轉(zhuǎn)移方程僅與上一階段的狀態(tài)轉(zhuǎn)移方程相關(guān)。因此設(shè) f0為 i1階段的狀態(tài)轉(zhuǎn)移方程， f1為 i階段的狀態(tài)轉(zhuǎn)移方程，這樣可以將二維數(shù)組簡化成一維數(shù)組。我們按照下述方法計算狀態(tài)轉(zhuǎn)移方程 f1： readln(v,n)。 for i:=1 to n do readln(x[i])。 fillchar(f0,sizeof(f0),0)。 //裝箱前，狀態(tài)轉(zhuǎn)移方程初始化 f0[0]:=true。 for i:=1 to n do //階段 i:按照物品數(shù)遞增的順序考慮裝箱情況 begin f1:=f0。 //i階段的狀態(tài)轉(zhuǎn)移方程初始化 if x[i]v then continue。 for j:=x[i] to v do //狀態(tài) j：枚舉所有可能的裝箱體積 if f0[jx[i]] then f1[j]:=true。 //若物品 i裝入箱子后的體積正好為 j,則物品 i裝入箱子 f0:=f1。 //記下當(dāng)前裝箱情況 end。 經(jīng)過上述運(yùn)算，最優(yōu)化問題轉(zhuǎn)化為判定性問題。再借用動態(tài)程序設(shè)計的思想，計算裝箱的最大體積 。顯然最小剩余空間為 vk: for k:=v downto 0 do //按照遞減順序枚舉所有可能的體積 if f1[k] then begin //若箱子能裝入體積為 i的物品，則輸出剩余空間 vi，并退出程序 writeln(vk)。 halt。 end。 【 例題 4】 合唱隊形 【 問題描述 】 N位同學(xué)站成一排，音樂老師要請其中的 (NK)位同學(xué)出列，使得剩下的 K位同學(xué)排成合唱隊形。 合唱隊形是指這樣的一種隊形：設(shè) K位同學(xué)從左到右依次編號為 1, 2, …, K ，他們的身高分別為 T1, T2, …, TK ，則他們的身高滿足 T1 T2 … Ti , Ti Ti+1 … TK (1≤i≤K) 。 你的任務(wù)是，已知所有 N位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊形。 【 輸入文件 】 輸入文件 N（ 2 ≤ N ≤ 100），表示同學(xué)的總數(shù)。第二行有 n個整數(shù)，用空格分隔，第 i個整數(shù) Ti（ 130 ≤ Ti ≤ 230）是第 i位同學(xué)的身高（厘米）。 【 輸出文件 】 輸出文件 ，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列。 【 樣例輸入 】 8 186 186 150 200 160 130 197 220 【 樣例輸出 】 4 【 數(shù)據(jù)規(guī)模 】 對于 50%的數(shù)據(jù)，保證有 n ≤ 20；對于全部的數(shù)據(jù)，保證有 n≤100。 【 算法分析 】 我們按照由左而右和由右而左的順序，將 n個同學(xué)的身高排成數(shù)列。如何分別在這兩個數(shù)列中尋求遞增的、未必連續(xù)的最長子序列，就成為問題的關(guān)鍵。設(shè) a 為身高序列，其中 a[i]為同學(xué) i的身高； b 為由左而右身高遞增的人數(shù)序列，其中 b[i]為同學(xué) 1‥ 同學(xué) i間（包括同學(xué) i）身高滿足遞增順序的最多人數(shù)。顯然 b[i]={b[j]|同學(xué) j的身高 同學(xué) i的身高 }+1； c為由右而左身高遞增的人數(shù)序列，其中 c[i]為同學(xué) n‥ 同學(xué) i間（包括同學(xué) i）身高滿足遞增順序的最多人數(shù)。顯然 c[i]={c[j]|同學(xué) j的身高 同學(xué) i的身高 }+1； 由上述狀態(tài)轉(zhuǎn)移方程可知，計算合唱隊形的問題具備了最優(yōu)子結(jié)構(gòu)性質(zhì)(要使 b[i]和 c[i]最大，子問題的解 b[j]和 c[k]必須最大 (1≤j≤i1 ， i+1≤k≤n))和重迭子問題的性質(zhì) (為求得 b[i]和 c[i]，必須一一查閱子問題的解 b[1]‥ b[i1]和c[i+1]‥ c[n])，因此可采用動態(tài)程序設(shè)計的方法求解。 顯然，合唱隊的人數(shù)為 (公式中同學(xué) i被重復(fù)計算，因此減 1)， n減去合唱隊人數(shù)即為解。 具體算法如下： readln(n)。 //讀學(xué)生數(shù) for i:=1 to n do read(a[i])。 //讀每個學(xué)生的身高 fillchar(b,sizeof(b),0)。fillchar(c,sizeof(c),0)。 //身高滿足遞增順序的兩個隊列初始化 for i:=1 to n do //按照由左而右的順序計算 b序列 begin b[i]:=1。 for j:=1 to i1 do if (a[i]a[j])and(b[j]+1b[i]) then b[i]:=b[j]+1。 end。 for i:=n downto 1 do //按照由右而左的順序計算 c序列 begin c[i]:=1。 for j:=i+1 to n do if (a[j]a[i])and(c[j]+1c[i])then c[i]:=c[j]+1。 end。 max:=0。 //計算合唱隊的人數(shù) max（其中 1人被重復(fù)計算 for i:=1 to n do if b[i]+c[i]max then max:=b[i]+c[i]。 writeln(nmax+1)。 //輸出出列人數(shù) 這個算法的時間復(fù)雜度為 O(n2)，在 1秒時限內(nèi)可解決 n≤100范圍內(nèi)的問題。 【 例題 5】 櫥窗布置（ Flower） 【 問題描述 】 假設(shè)以最美觀的方式布置花店的櫥窗，有 F束花，每束花的品種都不一樣，同時，至少有同樣數(shù)量的花瓶，被按順序擺成一行，花瓶的位置是固定的，并從左到右，從 1到 V順序編號， V是花瓶的數(shù)目