算法设计与分析 课件 5.6.2-动态规划应用-最长公共子序列-动态规划求解

信息工程大学算法设计与分析动态规划—最长公共子序列之动态规划求解国家级实验教学示范中心计算机学科组规划教材算法设计与分析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