第三次最長(zhǎng)公共子序列

1、實(shí)驗(yàn)三實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法一、實(shí)驗(yàn)?zāi)康呐c要求一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長(zhǎng)公共子序列問(wèn)題的算法；2、初步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題二、實(shí)驗(yàn)題若給定序列X=x1x2…xm，則另一序列Z=z1z2…zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1i2…ik使得對(duì)于所有j=12…k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。給定2個(gè)序列X和Y，當(dāng)

2、另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X=x1x2…xm和Y=y1y2…yn，找出X和Y的最長(zhǎng)公共子序列。三、實(shí)驗(yàn)步驟三、實(shí)驗(yàn)步驟程序代碼：packageunit1publicclassLCSpublicstaticvoidmain(String[]args)[]x=ABCBDAB[]y=BDCABAint[][]b=newint[x.length][y.length]int[][]c=ne

3、wint[x.length][y.length]lcs(xybc)lcs_put(x.length1y.length1xb)staticintlcs([]x[]yint[][]bint[][]c)intijintm=x.length1intn=y.length1f(i=1i=mi)c[i][0]=0f(i=1i=ni)c[0][i]=0f(i=1i=mi)f(j=1j=nj)if(x[i]==y[j])c[i][j]=c[i1][j1]