第三次最長公共子序列

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

2、另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X=x1x2…xm和Y=y1y2…yn，找出X和Y的最長公共子序列。三、實驗步驟三、實驗步驟程序代碼：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]