Pascal最長公共子序列問題.ppt

兩個模型,最長上升子列問題LIS； 最長公共子序列問題 ；,最長上升子列問題LIS,問題： 給出一個數(shù)列，要求從這個數(shù)列中找出一個最長的子列，使得這個子列的元素是嚴(yán)格單調(diào)上升的。 輸入： 第一行是一個數(shù)N，表示數(shù)列的長度。第二行是N個數(shù)，表示這個數(shù)列。其中N=300000。 輸出： 輸出僅有一個數(shù)，最長子列的長度。 樣例輸入： 6 3 7 2 4 6 8 樣例輸出： 4,分析:,1.考慮某個位,到達(dá)該位的最長上升序列只與其前面位的數(shù)字有關(guān)而與其后面位無關(guān),即具有子結(jié)構(gòu)性質(zhì); 2.設(shè)FI表示第I位數(shù)字的最長上升子序列長度,則FI值只與當(dāng)AJAI(JI)對應(yīng)的子序列有關(guān),容易獲得: FI=MAXFJ(AJAI(JI)+1 3.自底向上的方式計算問題的最優(yōu)值,顯然FI的初值為1,以下是對樣例的模擬操作分析,設(shè)ai為第i個數(shù)，fi為到第i個數(shù)最長上升子序列的大小，初始時fi=0，f1=1，,procedure main; var i,j,max:integer; begin max:=1; f1:=1; for i:=2 to n do begin for j:=1 to i-1 do求符合條件子列最大值 if (ajfi) then fi:=fj; inc(fi);子列最大值加1 if fimax then max:=fi; end; writeln(max); end;,算法效率：O(n2),注意觀察相同上升長度的子序列，如：長度為4的序列：3 5 6 8，3 4 5 7，3 4 5 6，影響后面最長子序列的是3 4 5 6序列。 證明： 因為6是長度為4序列中尾數(shù)最小的序列，如果一個數(shù)能加入長度為4的其它序列中也必定能加入該序列中。 故相同長度的子序列的有效信息是其序列中尾數(shù)最小的數(shù)。因此我們?nèi)绻黾右粋€數(shù)組記錄下每種序列結(jié)尾最小值，可不可以降低算法的時間復(fù)雜度呢？,序列 3 7 5 4 6 8 5 7 6 7 上升長度 1 2 2 2 3 4 3 4 4 5,建立一個數(shù)組sk來儲存所有長度為j的最長上升子序列的最后一個數(shù)字的最小值。即,sk=minaJ( FJ=K,1=J=I)。,對sk能發(fā)現(xiàn)什么性質(zhì)?,sK值是單調(diào)上升的!,改進(jìn)算法: 原算法的弊端是每次需要花O(n)的時間尋找最優(yōu)子序列. 由于sK值是單調(diào)上升 (1)考慮到ai元素時，用二分法在sk中尋找最大的一個k使skaI，讓fI=k+1,否則fI保留原值. (2)IF AI SfI THEN 更新SfI=AI 這樣，使算法的復(fù)雜度下降為O(nlog2n)。,分步變化示例如下:,(1),(2),(3),(4),(5),(6),program LIS; var n,i,max,k,e:integer;n數(shù)據(jù)長度，e記錄已知序列總數(shù)，max最優(yōu)值 num,dp,maxn:array 1300000 of integer;num記錄數(shù)據(jù)，dp記錄序列長度，maxn記錄每種序列結(jié)尾最小值 function find(x:integer):integer;二分查找，尋找當(dāng)前值所在的區(qū)間 var left,right,mid:integer; begin left:=1;right:=e; mid:=(left+right) div 2; while leftx then right:=mid-1 else left:=mid+1; mid:=(left+right) div 2; end; find:=mid-1; end;,begin assign(input,lis.in); reset(input); assign(output,lis.out); rewrite(output); readln(n); for i:=1 to n do maxni:=30000; for i:=1 to n do read(numi); dp1:=1; maxn1:=num1; e:=1; for i:=2 to n do 動態(tài)規(guī)劃過程 begin k:=find(numi)+1; if k+1dpi then dpi:=k+1; if k+1e then e:=k+1; if numimaxndpi then maxndpi:=numi; end;,max:=0; for i:=1 to n do if maxdpi then max:=dpi; writeln(max); close(output); end.,【問題】 求兩字符序列的最長公共字符子序列,問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一個嚴(yán)格遞增下標(biāo)序列，使得對所有的j=0，1，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。,考慮最長公共子序列問題如何分解成子問題，設(shè)A=“a0，a1，am-1”，B=“b0，b1，bm-1”，并Z=“z0，z1，zk-1”為它們的最長公共子序列。不難證明有以下性質(zhì)： （1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，zk-2”是“a0，a1，am-2”和“b0，b1，bn-2”的一個最長公共子序列； （2） 如果am-1bn-1，則若zk-1am-1，蘊涵“z0，z1，zk-1”是“a0，a1，am-2”和“b0，b1，bn-1”的一個最長公共子序列； （3） 如果am-1bn-1，則若zk-1bn-1，蘊涵“z0，z1，zk-1”是“a0，a1，am-1”和“b0，b1，bn-2”的一個最長公共子序列。 這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進(jìn)一步解決一個子問題，找“a0，a1，am-2”和“b0，b1，bm-2”的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，am-2”和“b0，b1，bn-1”的一個最長公共子序列和找出“a0，a1，am-1”和“b0，b1，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。,求解：引進(jìn)一個二維數(shù)組c，用cij記錄Xi與Yj 的LCS 的長度，bij記錄cij是通過哪一個子問題的值求得