【2018年必威体育精装版整理】动态规划.pptVIP

* 第5章 动态规划法 Page * 对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk)，Z是X的子序列当且仅当存在一个严格递增下标序列(i1, i2,…, ik)，使得对于所有j=1, 2, …, k，有zj=xij（1≤ij≤m）。 例如，序列X=(a, b, c, b, d, b)，子序列为Z=(a, c, b, d, b)，下标序列为(1, 3, 4, 5, 6) 给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题就是在序列X和Y的公共子序列中查找长度最长的公共子序列。 例如：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，它们的最长公共子序列为Z=(a, c, b, d, b)，在X中的递增下标序列是(1, 3, 4, 5, 6),在Y中的递增下标序列是(1, 2, 6, 7, 9) 3、最长公共子序列问题 * 第5章 动态规划法 Page * 要找出序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列，可按下述递推方式计算： （1）当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列； （2）当xm≠yn时，必须求解两个子问题：找出Xm-1和Y的最长公共子序列以及Xm和Yn-1的最长公共子序列，这两个公共子序列中的较长者即为X和Y的最长公共子序列。 用L[i][j]表示子序列Xi和Yj的最长公共子序列的长度，可得如下动态规划函数： L[0][0]=L[i][0]=L[0][j]=0(1≤i≤m,1≤j≤n) （式1） （式2） * 第5章 动态规划法 Page * 由此，把序列X={x1, x2,…, xm}和Y={y1, y2,…, yn}的最长公共子序列的有哪些信誉好的足球投注网站分为m个阶段，第1阶段，按照式2计算X1和Yj的最长公共子序列长度L[1][j]（1≤j≤n），第2阶段，按照式2计算X2和Yj的最长公共子序列长度L[2][j]（1≤j≤n），依此类推，最后在第m阶段，计算Xm和Yj的最长公共子序列长度L[m][j]（1≤j≤n），则L[m][n]就是序列Xm和Yn的最长公共子序列的长度。 * 第5章 动态规划法 Page * 为了得到序列Xm和Yn具体的最长公共子序列，设二维表S[m+1][n+1]，其中S[i][j]表示在计算L[i][j]的过程中的有哪些信誉好的足球投注网站状态，并且有： （式3） 若S[i][j]=1，表明ai=bj，则下一个有哪些信誉好的足球投注网站方向是S[i-1][j-1]；若S[i][j]=2，表明ai≠bj且L[i][j-1]≥L[i-1][j]，则下一个有哪些信誉好的足球投注网站方向是S[i][j-1]；若S[i][j]=3，表明ai≠bj且L[i][j-1]＜L[i-1][j]，则下一个有哪些信誉好的足球投注网站方向是S[i-1][j]。 * 第5章 动态规划法 Page * (a) 长度矩阵L (b) 状态矩阵S 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 2 2 2 1 2 2 2 2 2 0 1 1 2 2 2 2 2 2 2 2 0 3 2 1 1 2 1 2 1 1 3 0 1 2 2 2 2 2 2 2 2 3 0 3 1 2 2 2 2 2 2 2 4 0 1 2 3 3 3 3 3 3 3 4 0 3 3 1 1 3 1 3 1 1 5 0 1 2 3 3 3 3 4 4 4 5 0 3 3 3 2 2 2 1 2 2 6 0 1 2 3 4 4 4 4 5 5 6 0 3 3 1 1 3 1 2 1 1 例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立两个(m+1)×(n+1)的二维表L和表S，分别存放有哪些信誉好的足球投注网站过程中得到的子序列的长度和状态。 * 第5章 动态规划法 Page * (a) 长度矩阵L