算法設(shè)計與分析 課件 5.6.2-動態(tài)規(guī)劃應(yīng)用-最長公共子序列-動態(tài)規(guī)劃求解

信息工程大學(xué)算法設(shè)計與分析動態(tài)規(guī)劃—最長公共子序列之動態(tài)規(guī)劃求解國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版動態(tài)規(guī)劃解題步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。定義：c[i,j]為序列Xi=(x1,x2,…,xi)和Yj=(y1,y2,…,yj)的最長公共子序列的長度。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征c[i,j]為序列Xi=(x1,x2,…,xi)和Yj=(y1,y2,…,yj)的最長公共子序列的長度2.遞歸地定義最優(yōu)值

00000000000yjxmy1y2ynx1x2xi012nm120firstsecond

3.以自底向上的方式計算最優(yōu)值00000000000yjxmy1y2ynx1x2xi012nm120數(shù)組s[i,j]記錄最優(yōu)值對應(yīng)的信息如果xi=yj s[i,j]=1如果c[i-1,j]≥c[i,j-1]

s[i,j]=2否則 s[i,j]=3c[i,j-1]c[i-1,j]c[i-1,j-1]xiyj4.根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解實例分析：X=(B,D,A,B,A,C)Y=(B,A,D,B,C,D,A)0126345yjBADDBC51203467ABDxiABCA0000000

1

1

1

1

1

2

20000000

1

1

1

2

2

2

1

1

2

2

2

2

3

2

1

2

2

3

3

3

3

1

2

2

3

3

3

4

1

2

2

3

4

4

4如果xi=yj s[i,j]=“”如果c[i-1,j]≥c[i,j-1]

s[i,j]=“”否則 s[i,j]=“”實例分析：X=(B,D,A,B,A,C)Y=(B,A,D,B,C,D,A)0126345yjBADDBC51203467ABDxiABCA0000000

1

1

1

1

1

2

20000000

1

1

1

2

2

2

1

1

2

2

2

2

3

2

1

2

2

3

3

3

3

1

2

2

3

3

3

4

1

2

2

3

4

4

4得A得B得D得B最優(yōu)解：BDBAvoidLCSLength(intm，intn，char*x，char*y，int**c，int**s){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;s[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];s[i][j]=2;}else{c[i][j]=c[i][j-1];s[i][j]=3;}}}時間復(fù)雜度O(mn)/*構(gòu)造最優(yōu)解*/voidLCS(inti，intj，char*x，int**s){if(i==0||j==0)return;if(s[i][j]==1){LCS(i-1，j-1，x，s);cout<<x[i];}elseif(s[i][j]==2)LCS(i-1，j，x，s);elseLCS(i，j-1，x，s);}思考：以上計算過程可以優(yōu)化嗎？思考：數(shù)組s可以省去嗎？由于數(shù)組元素s[i][j]的值通過xi是否等于yj，c[i-1][j-1]，c[i-1][j]和c[i][j-1]確定，因此s數(shù)組可以省略。00000000000yjxmy1y2ynx1x2xi012nm120數(shù)組s[i,j]：記錄最優(yōu)解如果xi=yj s[i,j]=1如果c[i-1,j]≥c[i,j-1]

s[i,j]=2否則 s[i,j]=3c[i,j-1]c[i-1,j]c[i-1,j-1]xiyj思考：是否可以進一步優(yōu)化空間？在計算c[i][j]時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間(滾動數(shù)組)就可以計算出最長公共子序列的長度。00000000000yjxmy1y2ynx1x2xi012nm120c[i,j-1]c[i-1,j]c[i-1,j-1]xiyj判斷：在求解X和Y的最長公共子序列時，X作為行或者列都是可以的。A.錯誤B.正確給定兩個單詞

word1

和

word2，找到使得

word1

和

word2

相同所需的最小步數(shù)，每步可以刪除任意一個字符串中的一個字符。

示例：輸入:"sea","eat