算法設(shè)計與分析-動態(tài)規(guī)劃

算法設(shè)計與分析

DesignandAnalysisofAlgorithms1難點22023/11/21第八章動態(tài)規(guī)劃主要內(nèi)容投資分配問題動態(tài)規(guī)劃地設(shè)計技術(shù)背包問題最優(yōu)解特征分析與階段劃分計算模型地建立矩陣邊乘問題最長公子序問題最大子段與問題32023/11/21第八章動態(tài)規(guī)劃主要內(nèi)容投資分配問題動態(tài)規(guī)劃地設(shè)計技術(shù)背包問題矩陣邊乘問題最長公子序問題最大子段與問題4==動態(tài)規(guī)劃地設(shè)計技術(shù)==動態(tài)規(guī)劃地基本設(shè)計思想將待求解問題分解成若干個子問題,分階段求解子問題,前一階段子問題地解成為求后續(xù)階段子問題地解地計算信息,最后用這些子問題地最優(yōu)解構(gòu)造出原問題地最優(yōu)解。適合用動態(tài)規(guī)劃求解地問題地特征(一)子問題重疊①子問題重復(fù)②子問題地解在下一階段決策,延續(xù)子問題多次使用s一一s一二s一三s一四s二一s二二smaxs原問題第一階段第二階段第三階段最優(yōu)解(二)最優(yōu)子結(jié)構(gòu)一個問題地最優(yōu)解包含著它地子問題地最優(yōu)解5例八-一有一個數(shù)塔,結(jié)點數(shù)字為其權(quán)值,按自頂向下（或自底向上）方式行走,經(jīng)過地每一個結(jié)點,可以選擇向左或向右走,到達底（或頂部）,求一條自頂向下（或自底向上）地路徑,所經(jīng)過結(jié)點權(quán)值與最大。八一一一零三一八上向底自(三)貪心八一一一四一零五八三一七九四一八七一二六一六(一)數(shù)塔八一四八九一二自頂向下(二)貪心問題分析==動態(tài)規(guī)劃地設(shè)計技術(shù)==6八一一一四一零五八三一七九四一八七一二六一六(四)數(shù)塔--動態(tài)規(guī)劃二一二九二一二零三九三四二九四八五零五八一層第一階段二層第二階段三層第三階段四層五層第四階段==動態(tài)規(guī)劃地設(shè)計技術(shù)==第一階段三+一八>三+七,選擇結(jié)點一八,最優(yōu)值二一;一七+七<一七+一二,選擇結(jié)點一二,最優(yōu)值二九;九+一二>九+六,選擇結(jié)點一二,最優(yōu)值二一;四+六<四+一六,選擇結(jié)點一六,最優(yōu)值二零。問題分析第二階段一零+二一<一零+二九,選擇結(jié)點一七;五+二九>五+二一,選擇結(jié)點一七;八+二一>八+二零,選擇結(jié)點九。第三階段一一+三九>一一+三四,選擇結(jié)點一零;一四+三四>一四+二九,選擇結(jié)點五。第四階段:八+五零>八+四八,選擇結(jié)點一一。最優(yōu)解所經(jīng)歷地結(jié)點:八一一一零一七一二7八一一一四一零五八三一七九四一八七一二六一六(四)數(shù)塔--動態(tài)規(guī)劃二一二九二一二零三九三四二九四八五零五八一層第一階段二層第二階段三層第三階段四層五層第四階段==動態(tài)規(guī)劃地設(shè)計技術(shù)==最優(yōu)解:問題分析最優(yōu)解所經(jīng)歷地結(jié)點:八一一一零一七一二三.二算法與數(shù)據(jù)結(jié)構(gòu)==用貪心法求問題地解==計算模型(一)存儲結(jié)構(gòu): data[n][n]存儲原始數(shù)據(jù)信息; r[n][n]存儲每一階段地路徑地計算結(jié)果; path[n][n]存儲下一步最優(yōu)結(jié)點列坐標(biāo)。(二)計算:階段最優(yōu)r[i][j]=max{r[i+一][j],r[i+一][j+一]}+data[i][j]i=n-二,…,一;j≤i下一最優(yōu)子結(jié)點地列坐標(biāo)最優(yōu)解data[一][一]data[二][j]data[i+一][j]……,i=j=一,j=j+path最優(yōu)值 r[一][一]動態(tài)規(guī)劃算法設(shè)計地基本步驟找出最優(yōu)解地質(zhì),并刻畫其結(jié)構(gòu)特征。按最優(yōu)解地質(zhì),劃分子問題及演算地階段,遞推求解最優(yōu)解。以自底向上或自頂向下地記憶化方法(備忘錄法)計算出最優(yōu)值。根據(jù)每階段推算出地局部最優(yōu)解,構(gòu)造出全局最優(yōu)解。92023/11/21第八章動態(tài)規(guī)劃主要內(nèi)容投資分配問題動態(tài)規(guī)劃地設(shè)計技術(shù)背包問題矩陣邊乘問題最長公子序問題最大子段與問題三.二算法與數(shù)據(jù)結(jié)構(gòu)==投資分配問題==例八-二設(shè)有n萬元錢,投資m個項目,將xi萬元錢投入第i個項產(chǎn)生地效益為fi(xi),i=一,二,…,m。請問如何分配這n萬元錢,使得投資地總效益最高？ 問題分析依題意,可以列出該問題地方程:目地方程 s.t. 三.二算法與數(shù)據(jù)結(jié)構(gòu)==投資分配問題==第一階段,給項目一投資,列出項目一投資地最優(yōu)投資方案,其獲利方程可表示為g一(x)=f一(xi),xi=零,一,二,三,四,五五萬元有三種分配情況:①全部投資給某一個項目;②按比例投資給任意兩個項;③按比例投資給三個項目;三.二算法與數(shù)據(jù)結(jié)構(gòu)==投資分配問題==x第二階段,加入項目二,在第一階段地基礎(chǔ)上求出兩個項目地分配方案,獲利方程可表示g二(x)=,如 g二(一)=max{f二(零)+g一(一),f二(一)+g一(零)}, g二(二)=max{f二(零)+g一(二),f二(一)+g一(一),f二(二)+g一(零)},x-三.二算法與數(shù)據(jù)結(jié)構(gòu)==投資分配問題==第三階段,加入項目三,在第二階段地基礎(chǔ)上求出三個項目地分配本方案,獲利方程可表示g三(xi)=。xxx-x-三.二算法與數(shù)據(jù)結(jié)構(gòu)計算模型(一)遞推方程設(shè)k為階段變量,零≤k≤m由問題分析可得遞推方程與邊界條件:(二)存儲設(shè)有m個項目,投資n萬元。最多m個階段。a[][]表示某階段最大獲利情況下分配給某個項目資金。a[i][j]?f[]存儲某項目初始投資所獲得利潤。f[i]表示投資i萬元給某項目所獲得地利潤(數(shù)組值)。t[]存儲當(dāng)前投資額地最大利潤g[]存儲每一階段地最優(yōu)方案。運算完畢后,更新g[k]=t[k]。gain[]存儲整個投資地最優(yōu)分配方案。==投資分配問題==三.二算法與數(shù)據(jù)結(jié)構(gòu)計算模型(三)求解最優(yōu)方案a[m][n]就表示投資n萬元,得到最大獲利后,分配項目m地資金。設(shè)rest=n,令gain[m]=a[m][rest]表示最后一個項目在最優(yōu)分配方案地最大配額。rest=rest–a[m][n]a[m-一][rest]就表示給第m-一個項目分配rest取得最大利潤后,分配給第m-一個項目資金。rest=rest–a[m-一][rest]表示減去最后兩個項目后地投資,則a[m-二][rest]就表示給第m-二個項目分配rest取得最大利潤后,分配給第m-二個項目資金。依此類推,……就可以找到最優(yōu)解==投資分配問題==三.二算法與數(shù)據(jù)結(jié)構(gòu)==投資分配問題==n+一次

=(m-一)*(C二*(n+二)*(n+一)/二+(C一+C三)*(n+一))m次n+一次T(n)=O(m*n二)172023/11/21第八章動態(tài)規(guī)劃主要內(nèi)容投資分配問題動態(tài)規(guī)劃地設(shè)計技術(shù)背包問題矩陣邊乘問題最長公子序問題最大子段與問題三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-三背包問題(KnapsackProblem)。給定n個重量為w一,w二,…wn,價值為v一,v二,…vn地物品與一個承重為W地背包,求將這些物品地某些裝入背包,在不超出重量W地情況下,價值最高地裝法。問題分析依題意,可以得到如下地約束關(guān)系:目地函數(shù)s.t. ==背包問題==背包問題屬于線規(guī)劃問題。如果線規(guī)劃問題地變量都是非負(fù)整數(shù),則稱為整數(shù)規(guī)劃問題。背包問題就是整數(shù)規(guī)劃問題。限制所有地xi=零或xi=一時地背包問題稱為零-一背包問題。三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-三背包問題(KnapsackProblem)。最優(yōu)子結(jié)構(gòu)地證明

==背包問題==設(shè)(y一,y二,…,yn)是所給零-一背包問題地一個最優(yōu)解。去掉y一,有

則(y二,…,yn)是(二)式地一個最優(yōu)解。若不成立。設(shè)(z二,…,zn)是(二)式地一個最優(yōu)解,則有(一)(二)>且

(y一,z二,…,zn)是所給零-一背包問題地一個更優(yōu)解,從而(y一,y二,…,yn)不是所給零-一背包問題地最優(yōu)解矛盾,得證三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-三背包問題(KnapsackProblem)。子集合及階段劃分:將每加入一個物品看成一個階段。 將背包地承重劃分為不同地重量。==背包問題==背包地限重為w(w≤W),求前i(一≤i≤n)個物品裝包地最優(yōu)解。設(shè)前i-一個物品裝包地最優(yōu)值為fi-一(w),則有兩種情況:裝入i物品與不裝入i物品,則有fi(w)=max{fi-一(w),fi-一(w-wi)+vi}。當(dāng)wi>w時,fi(w)=fi-一(w)當(dāng)背包沒有裝入物品時,最優(yōu)價值為零;非等分子問題等差遞增問題拆包當(dāng)背包承載為零時,不能裝入物品,最優(yōu)價值也為零。三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-三背包問題(KnapsackProblem)。計算模型(一)遞推方程==背包問題==(二)存儲i—表示物品編號,j表示背包當(dāng)前地限載重量W—表示背包最大承載重量w[]—表示物品重量,如第i個物品地重量為w[i]v[]—表示物品價值,如第i個物品地價值為v[i]f[][]—表示在某限載情況下,背包最優(yōu)裝載地價值,如f[i][j]指在背包限載重量為j地情況下,第i階段(前i個物品)最優(yōu)裝載地價值。三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-二背包問題(KnapsackProblem)。計算模型==背包問題==第一階段,新增物品i=一,有f一(一)=f零(一)=零;//限重為一,小于w[一](w[一]=二)f一(二)=max{f零(二),f零(二-w[一])+v[一]}=max{零,f零(零)+一二}=一二;f一(三)=max{f零(三),f零(三-w[一])+v[一]}=max{零,f零(一)+一二}=一二;同理有f一(四)=一二;f一(五)=一二;第二階段,新增物品i=二,有f二(一)=max{f一(一),f一(一-w[二])+v[二]}=max{零,f一(零)+一零}={零,一零}=一零;f二(二)=max{f一(二),f一(二-w[二])+v[二]}=max{一二,f一(一)+一零}={一二,一零}=一二;f二(三)=max{f一(三),f一(三-w[二])+v[二]}=max{一二,f一(二)+一零}={一二,二二}=二二;同理有f一(四)=二二;f一(五)=二二;第三階段,新增物品i=三,有f三(一)=f二(一)=一零;//限重為一,小于w[三](w[三]=三)f三(二)=f二(二)=一二;//限重為二,小于w[三](w[三]=三)f三(三)=max{f二(三),f二(三-w[三])+v[三]}=max{二二,f二(零)+二零}={二二,二零}=二二;f三(四)=max{f二(四),f二(四-w[三])+v[三]}=max{二二,f二(一)+二零}={二二,三零}=三零;f三(五)=max{f二(五),f二(五-w[三])+v[三]}=max{二二,f二(二)+二零}={二二,三二}=三二;三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-三背包問題(KnapsackProblem)。==背包問題==五-w[四]=三三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-三背包問題(KnapsackProblem)。==背包問題==復(fù)雜度分析(一)問題地輸入規(guī)模是n個重量w[n],n個價值v[n]及背包總承載重量W(二)第一階段動態(tài)規(guī)劃前后兩部分合起來地初始化是W次除去第一階段動態(tài)規(guī)劃外,還有n-一階段動態(tài)規(guī)劃,其均包含W次優(yōu)化過程,可以表示如下:

(三)回溯推導(dǎo)最優(yōu)解所需要地計算次數(shù)為n次?？偩C上所述,可得T(n)=W+(n-一)(W+一)+n=n*W+二*n-一=θ(n*W)log二W,若設(shè)k=log二W,則有W=二k。當(dāng)背包承載地重量很大時,它地時間復(fù)雜度實際上是T(n)=θ(n*二k)252023/11/21第八章動態(tài)規(guī)劃主要內(nèi)容投資分配問題動態(tài)規(guī)劃地設(shè)計技術(shù)背包問題矩陣連乘問題最長公子序問題最大子段與問題三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。設(shè)M一,M二,…Mn為n個矩陣地序列,其Mi為ri×ri+一階矩陣,i=一,二,…,n。這個矩陣鏈地輸入是向量R=<r零,r一,…,rn>,因為矩陣運算滿足結(jié)合律,所以運算結(jié)果與計算地順序無關(guān),但是不同運算順序,會造成運算時地乘法次數(shù)地不同。求以哪種乘法次序運算,使得基本運算地總次數(shù)最少。==矩陣連乘問題==問題分析多個矩陣連乘運算是滿足結(jié)合律例:M一[五*二零]*M二[二零*五零]*M三[五零*一]*M四[一*一零零]可能地運算次序為:C[((M一*M二)*M三)*M四]=五*二零*五零+五*五零*一+五*一*一零零=五七五零C[M一*(M二*(M三*M四))]=五零*一*一零零+二零*五零*一零零+五*二零*一零零=一一五零零零C[(M一*(M二*M三))*M四]=二零*五零*一+五*二零*一+五*一*一零零=一六零零三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==問題分析(一)階段劃分第一階段:一個矩陣相乘地計算量為零;第二階段:計算兩個相鄰矩陣相乘地計算量,三組第三階段:計算兩個相鄰矩陣相乘地結(jié)果與第三個矩陣相乘地計算量,二組第四階段:計算三個矩陣相乘地結(jié)果與第四個矩陣相乘地計算量,一組三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==問題分析(二)階段決策 設(shè)矩陣大小為:M一為r一×r二,M二為r二×r三,M三為r三×r四,M四為r四×r五一個矩陣"相乘"有四種情況m一一=零;m二二=零;m三三=零;m四四=零;二個矩陣相乘有三種情況:m一二=r一*r二*r三;m二三=r二*r三*r四;m三四=r三*r四*r五;三個矩陣連續(xù)相乘有二種情況:m一三=min{m一二+m三三+r一*r三*r四,m一一+m二三+r一*r二*r四}m二四=min{m二三+m四四+r二*r四*r五,m二二+m三四+r二*r三*r五}四個矩陣相乘矩陣有１種情況:m一四=min{m一一+m二四+r一*r二*r五,m一二+m三四+r一*r三*r五,m一三+m四四+r一*r四*r五}上一階段地增益本階段地增益三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==數(shù)學(xué)模型設(shè)求n個矩陣連乘基本運算次數(shù)為C[M一*M二*M三*……*Mn],其,Mi為ri*ri+一階矩陣,i=一,二,三,…,n。設(shè)mi,j是計算Mi*Mi+一*…Mj地最少乘法次數(shù)(一≤i≤j≤n),對mi,j有公式:零 i=jri*ri+一*ri+二 j=i+一min(mi,k+mk+一,j+ri*rk+一*rj+一) i≤k<j,i<j因為有i≤j,所以,可設(shè)j=i+s,s=零,一,…,n-一,則有mi,j=mi,i+s。記錄最優(yōu)解用二維矩陣ij(n*n)來存儲使mij為最小值時地k值一一=零一二=一一三=一一四=三二二=零二三=二二四=三三三=零三四=三四四=零M一[五*二零]*M二[二零*五零]*M三[五零*一]*M四[一*一零零](M一*(M二*M三))*M四三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==算法設(shè)計與描述(一)遞歸算法print三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==算法設(shè)計與描述(一)遞歸算法intcourse(inti,intj){intu,t;if(i=j)return零;if(i=j-一){[i][i+一]=i;return（r[i]*r[i+一]*r[i+二]）;}u=course(i,i)+course(i+一,j)+r[i]*r[i+一]*r[j+一];[i][j]=i;for(intk=i+一;k<j;k++){t=course(i,k)+course(k+一,j)+r[i]*r[k+一]*r[j+一];if(t<u){u=t;[i][j]=k;}}returnu;}零增益已知增益新增增益這種選擇下地增益記錄這種分割點償試其它分割地方法記錄每種選擇下地增益根據(jù)不同地增益行最優(yōu)化選擇三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==算法分析(一)遞歸算法

==二O(二n-一)一-四一-一二-四一-二三-四一-三四-四二-二三-四二-三四-四一-一二-三一-二三-三一-一二-二三-三四-四定理:當(dāng)n>一時,T(n)=Ω(二n-一)證:當(dāng)n=二時,T(二)≥c=c一二二-一,c一=c/二.假設(shè)對于,T(k)≥c一二k-一,則T(n)≥c’(n-一)+≥c’(n-一)+=c’(n-一)+c一(二n-四)≥c一二n-一三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==算法設(shè)計與描述(二)改遞歸算法m[][]記錄運算次數(shù)course(inti,intj){if(m[i][j]>零)returnm[i][j];if(i=j)return零;if(i=j-一){[i][i+一]=i;m[i][j]=r[i]*r[i+一]*r[i+二];returnm[i][j];}intu=course(i,i)+course(i+一,j)+r[i]*r[i+一]*r[j+一];[i][j]=i;for(intk=i+一;k<j;k++){intt=course(i,k)+course(k+一,j)+r[i]*r[k+一]*r[j+一];if(t<u){u=t;[i][j]=k;}}m[i][j]=u;returnu;}三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==算法設(shè)計與描述(二)改遞歸算法三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==算法設(shè)計與描述(二)非遞歸算法main(){intn,r[一零零],m[一零零][一零零],[一零零][一零零];input(n);for(i=一;i<=n+一;i++)input(r[i]);/初始化化數(shù)組與m。/for(i=一;i<n;i++){m[i][i]=零; \s=零\m[i][i+一]=r[i]*r[i+一]*r[i+二];\s=一\[i][i+一]=i+一;}第一階段動態(tài)規(guī)劃第二階段動態(tài)規(guī)劃三.二算法與數(shù)據(jù)結(jié)構(gòu)例八-四矩陣連乘問題。==矩陣連乘問題==算法設(shè)計與描述(二)非遞歸算法m[n][n]=零;for(s=二;s<=n-一;s++)/動態(tài)規(guī)劃過程/for(i=一;i<n-s+一;i++){j=i+s;m[i][j]=m[i][i]+m[i+一][j]+r[i]*r[i+一]*r[j+一];[i][j]=i;for(k=i+一;k<j;k++){t=m[i][k]+m[k+一][j]+r[i]*r[k+一]*r[j+一];if(t<m[i][j]){m[i][j]=t;[i][j]=k;}}}print("Theleastcalculatequantity:"m[一][n]);for(i=一;i<=n;i++){print("換行符");for(j=一;j<=n;j++)print([i][j]);}}O(n三)372023/11/21第八章動態(tài)規(guī)劃主要內(nèi)容投資分配問題動態(tài)規(guī)劃地設(shè)計技術(shù)背包問題矩陣連乘問題最長公子序問題最大子段與問題例八-四求數(shù)列地最大子段與。給定n個元素地整數(shù)列（可能有負(fù)整數(shù)）a一,a二,···,an,求形如:

ai,ai+一,···,aji,j=一,二,···,n,i<=j

地子段與,使其為最大。當(dāng)所有整數(shù)均為負(fù)整數(shù)時定義其最大字段與為零。

如(a一,a二,a三,a四,a五,a六)=(-二,一一,-四,一三,-五,-二)時最大子段與為:a二+a三+a四=二零2023/11/2138突出階段地動態(tài)規(guī)劃應(yīng)用2023/11/2139開始設(shè)置初始位置best_i\best_j,最大子段與sum,當(dāng)前子段與this_sum順次選取集合元素j=零ton-一計算當(dāng)前子段與this_sumthis_sum[j]=this_sum[j-一]+a[j]sum[j]=this_sum[j]bset_i=ibest_j=j比較sum[j]<this_sum[j]this_sum[j]<零新啟點i=j+一輸入數(shù)字序列輸出最大子段結(jié)束是否是否算法一2023/11/2140算法改（算法二）2023/11/2141算法實現(xiàn)422023/11/21第八章動態(tài)規(guī)劃主要內(nèi)容投資分配問題動態(tài)規(guī)劃地設(shè)計技術(shù)背包問題矩陣連乘問題最長公子序問題最大子段與問題2023/11/2143問題分析若A地長度為n,若B地長度為m,則A地子序列有:一+二+三+……+n=二n-一B地子序列有:一+二+三+……+m=二m-一如采用枚舉策略,當(dāng)m=n時,行串比較:一*一+二*二+三*三+……+n*n<二二n次,耗時太多,不可取。此問題不可能簡單地分解成幾個獨立地子問題,也不能用分治法來解。所以,我們只能用動態(tài)規(guī)劃地方法去解決。例八-五求兩個字符序列地最長公字符子序列X="ABCBDAB"Y="BCDB"2023/11/2144算法設(shè)計一．遞推關(guān)系分析設(shè)A="a零,a一,…,am-一",B="b零,b一,…,bn-一",A,B地最長公子序列為:Z="z零,z一,…,zk-一"。有以下結(jié)論:一）如果am-一=bn-一,則zk-一=am-一=bn-一,且"z零,z一,…,zk-二"是"a零,a一,…,am-二"與"b零,b一,…,bn-二"地一個最長公子序列;二）如果am-一≠bn-一,則若zk-一≠am-一,蘊涵"z零,z一,…,zk-一"是"a零,a一,…,am-二"與"b零,b一,…,bn-一"地一個最長公子序列;三）如果am-一≠bn-一,則若zk-一≠bn-一,蘊涵"z零,z一,…,zk-一"是"a零,a一,…,am-一"與"b零,b一,…,bn-二"地一個最長公子序列。2023/11/2145一）如果i=零或j=零,c[i][j]=零;二）如果i,j>零,且a[i-一]=b[j-一],c[i][j]=c[i-一][j-一]+一;三）如果i,j>零,且a[i-一]≠b[j-一],c[i][j]=max(c[i-一][j]),c[i][j-一])。

j一二三四五ibjBDCAB零ai零零零零零一A零零零零一二B零一一一一三C零一一二二四B零一一二二五D零一二二二六A零一二二三七B零一二二三六零A零零一一二二二二三三三三三四四四二．存儲,子問題合并最長公子序列地長度,計算c[i][j]可遞歸地表述如下:2023/11/2146lcs_len(int

i,j)//計算最優(yōu)值{

if(i=零orj=零)

c[i][j]=零;elseif(a[i-一]=b[j-一])c[i][j]=

lcs_len(i-一,j-一)+一

;elsec[i][j]=max(lcs_len(i,j-一),lcs_len(i-一,j));}buile_lcs(k,i,j);//構(gòu)造最長公子序列{if（i=零orj=零）return;

if（c[i][j]=c[i-一][j]） buile_lcs(k,i-一,j);elseif（c[i][j]=c[i][j-一]） buile_lcs(k,i,j-一);else{str[k-一]=a[i-一];

buile_lcs(k-一,i-一,j-一);}}j一二三四五ibjBDCAB零ai零零零零零一A零零零零一二B零一一一一三C零一一二二四B零一一二二五D零一二二二六A零一二二三七B零一二二三六零A零零一一二二二二三三三三三四四四2023/11/2147算法(非遞歸形式)intNum=一零零

char

a[Num],b[Num],str[Num],c[Num][Num];main()

{intm,n,k;print

("Enter

two

string");

input(a,b);m=strlen(a);n=strlen(b),

k=lcs_len(n,m);buile_lcs(k,n,m);print(str);

}2023/11/2148算法(非遞歸)n=一零零

char

a[n],b[n],str[n];lcs_len(char

a[],

char

b[],

int

c[

][

n])

{int

m,n,i,j;

print

("Enter

two

string");

input(a,b);

m=strlen(a);n=strlen(b);for

(i=零;i<=m;i++)

c[i][零]=零;

for

(i=零;i<=n;i++)

c[零][i]=零;

for

(i=一;i<=m;i++)

for

(j=一;j<=n;j++)

if

(a[i-一]=b[j-一])

c[i][j]=c[i-一][j-一]+一;

else

if

(c[i-一][j]>=c[i][j-一])

c[i][j]=c[i-一][j];

else

c[i][j]=c[i][j-一];

retu