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

00000000000yjxmy1y2ynx1x2xi012nm120firstsecond

3.以自底向上的方式計算最優值00000000000yjxmy1y2ynx1x2xi012nm120數組s[i,j]記錄最優值對應的信息如果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.根據計算最優值時得到的信息，構造最優解實例分析：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最優解：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;}}}時間復雜度O(mn)/*構造最優解*/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);}思考：以上計算過程可以優化嗎？思考：數組s可以省去嗎？由于數組元素s[i][j]的值通過xi是否等于yj，c[i-1][j-1]，c[i-1][j]和c[i][j-1]確定，因此s數組可以省略。00000000000yjxmy1y2ynx1x2xi012nm120數組s[i,j]：記錄最優解如果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思考：是否可以進一步優化空間？在計算c[i][j]時，只用到數組c的第i行和第i-1行。因此，用2行的數組空間(滾動數組)就可以計算出最長公共子序列的長度。00000000000yjxmy1y2ynx1x2xi012nm120c[i,j-1]c[i-1,j]c[i-1,j-1]xiyj判斷：在求解X和Y的最長公共子序列時，X作為行或者列都是可以的。A.錯誤B.正確給定兩個單詞

word1

和

word2，找到使得

word1

和

word2

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

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