Pascal最長(zhǎng)公共子序列問(wèn)題.ppt

兩個(gè)模型,最長(zhǎng)上升子列問(wèn)題LIS； 最長(zhǎng)公共子序列問(wèn)題 ；,最長(zhǎng)上升子列問(wèn)題LIS,問(wèn)題： 給出一個(gè)數(shù)列，要求從這個(gè)數(shù)列中找出一個(gè)最長(zhǎng)的子列，使得這個(gè)子列的元素是嚴(yán)格單調(diào)上升的。 輸入： 第一行是一個(gè)數(shù)N，表示數(shù)列的長(zhǎng)度。第二行是N個(gè)數(shù)，表示這個(gè)數(shù)列。其中N=300000。 輸出： 輸出僅有一個(gè)數(shù)，最長(zhǎng)子列的長(zhǎng)度。 樣例輸入： 6 3 7 2 4 6 8 樣例輸出： 4,分析:,1.考慮某個(gè)位,到達(dá)該位的最長(zhǎng)上升序列只與其前面位的數(shù)字有關(guān)而與其后面位無(wú)關(guān),即具有子結(jié)構(gòu)性質(zhì); 2.設(shè)FI表示第I位數(shù)字的最長(zhǎng)上升子序列長(zhǎng)度,則FI值只與當(dāng)AJAI(JI)對(duì)應(yīng)的子序列有關(guān),容易獲得: FI=MAXFJ(AJAI(JI)+1 3.自底向上的方式計(jì)算問(wèn)題的最優(yōu)值,顯然FI的初值為1,以下是對(duì)樣例的模擬操作分析,設(shè)ai為第i個(gè)數(shù)，fi為到第i個(gè)數(shù)最長(zhǎng)上升子序列的大小，初始時(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),注意觀(guān)察相同上升長(zhǎng)度的子序列，如：長(zhǎng)度為4的序列：3 5 6 8，3 4 5 7，3 4 5 6，影響后面最長(zhǎng)子序列的是3 4 5 6序列。 證明： 因?yàn)?是長(zhǎng)度為4序列中尾數(shù)最小的序列，如果一個(gè)數(shù)能加入長(zhǎng)度為4的其它序列中也必定能加入該序列中。 故相同長(zhǎng)度的子序列的有效信息是其序列中尾數(shù)最小的數(shù)。因此我們?nèi)绻黾右粋€(gè)數(shù)組記錄下每種序列結(jié)尾最小值，可不可以降低算法的時(shí)間復(fù)雜度呢？,序列 3 7 5 4 6 8 5 7 6 7 上升長(zhǎng)度 1 2 2 2 3 4 3 4 4 5,建立一個(gè)數(shù)組sk來(lái)儲(chǔ)存所有長(zhǎng)度為j的最長(zhǎng)上升子序列的最后一個(gè)數(shù)字的最小值。即,sk=minaJ( FJ=K,1=J=I)。,對(duì)sk能發(fā)現(xiàn)什么性質(zhì)?,sK值是單調(diào)上升的!,改進(jìn)算法: 原算法的弊端是每次需要花O(n)的時(shí)間尋找最優(yōu)子序列. 由于sK值是單調(diào)上升 (1)考慮到ai元素時(shí)，用二分法在sk中尋找最大的一個(gè)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ù)長(zhǎng)度，e記錄已知序列總數(shù)，max最優(yōu)值 num,dp,maxn:array 1300000 of integer;num記錄數(shù)據(jù)，dp記錄序列長(zhǎng)度，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 動(dòng)態(tài)規(guī)劃過(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.,【問(wèn)題】 求兩字符序列的最長(zhǎng)公共字符子序列,問(wèn)題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列，使得對(duì)所有的j=0，1，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個(gè)子序列。,考慮最長(zhǎng)公共子序列問(wèn)題如何分解成子問(wèn)題，設(shè)A=“a0，a1，am-1”，B=“b0，b1，bm-1”，并Z=“z0，z1，zk-1”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)： （1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，zk-2”是“a0，a1，am-2”和“b0，b1，bn-2”的一個(gè)最長(zhǎng)公共子序列； （2） 如果am-1bn-1，則若zk-1am-1，蘊(yùn)涵“z0，z1，zk-1”是“a0，a1，am-2”和“b0，b1，bn-1”的一個(gè)最長(zhǎng)公共子序列； （3） 如果am-1bn-1，則若zk-1bn-1，蘊(yùn)涵“z0，z1，zk-1”是“a0，a1，am-1”和“b0，b1，bn-2”的一個(gè)最長(zhǎng)公共子序列。 這樣，在找A和B的公共子序列時(shí)，如有am-1=bn-1，則進(jìn)一步解決一個(gè)子問(wèn)題，找“a0，a1，am-2”和“b0，b1，bm-2”的一個(gè)最長(zhǎng)公共子序列；如果am-1!=bn-1，則要解決兩個(gè)子問(wèn)題，找出“a0，a1，am-2”和“b0，b1，bn-1”的一個(gè)最長(zhǎng)公共子序列和找出“a0，a1，am-1”和“b0，b1，bn-2”的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。,求解：引進(jìn)一個(gè)二維數(shù)組c，用cij記錄Xi與Yj 的LCS 的長(zhǎng)度，bij記錄cij是通過(guò)哪一個(gè)子問(wèn)題的值求得