【Chapter 5】Dynamic Programming（上）

• 算法结构

Dynamic Programming

考前最后一节课明确提到这一部分会考矩阵链乘问题（Matrix Chain）或是最长公共子序列问题（Longest Common Subsequence, LCS），考察的形式是填写DP的Table，因此以blog的方式对复习的过程进行记录，并查缺补漏。

Matrix Chain

问题描述： 给定

n

n

n个矩阵的序列

< A 1 , A 2 , . . . , A n >

，需要计算其矩阵乘积

A

1

A

2

.

.

.

A

n

A_1A_2…A_n

A1​A2​…An​。

计算多个矩阵链乘的积可以使用括号来指定计算次序，每一个括号内的矩阵相乘调用标准的矩阵乘法。不同括号化方式产生不同的计算成本。 因此，矩阵链乘实质上是一个最优括号化问题。

用动态规划可以获得多项式解。

Step1：最优的括号化结构（描述最优解的结构性质）

  • 将

    A

    i

    A

    i

    +

    1

    .

    .

    .

    A

    j

    A_iA_{i+1}…A_j

    Ai​Ai+1​…Aj​的积简记为

    A

    i

    .

    .

    .

    j

    A_{i…j}

    Ai…j​，其中

    1

    ≤

    i

    ≤

    j

    ≤

    n

    1\leq{i}\leq{j}\leq{n}

    1≤i≤j≤n；

  • 设

    A

    i

    .

    .

    .

    j

    A_{i…j}

    Ai…j​的最优括号化是在

    A

    k

    A_k

    Ak​和

    A

    k

    +

    1

    A_{k+1}

    Ak+1​之间进行分裂产生的，要求

    i

    ≤

    k

    ≤

    j

    −

    1

    i\leq{k}\leq{j-1}

    i≤k≤j−1；

  • 对于某个

    k

    k

    k，先计算

    A

    i

    .

    .

    .

    k

    A_{i…k}

    Ai…k​和

    A

    k

    +

    1…

    j

    A_{k+1…j}

    Ak+1…j​，再计算两个积相乘产生积

    A

    i

    .

    .

    .

    j

    A_{i…j}

    Ai…j​，两部分积合并的代价是

    p

    i

    −

    1

    ⋅

    p

    k

    ⋅

    p

    j

    p_{i-1}\cdot{p_k}\cdot{p_j}

    pi−1​⋅pk​⋅pj​，其中

    p

    i

    −

    1

    p_{i-1}

    pi−1​是矩阵

    A

    i

    A_i

    Ai​的行，

    p

    k

    p_k

    pk​是矩阵

    A

    k

    A_k

    Ak​的列，

    p

    j

    p_j

    pj​是矩阵

    A

    j

    A_j

    Aj​的列。

最优括号化的成本为：计算

A

i

.

.

.

k

A_{i…k}

Ai…k​的成本 + 计算

A

k

+

1…

j

A_{k+1…j}

Ak+1…j​的成本 + 两部分积合并的成本。获得最优括号化方案的关键在于，前后缀子链

A

i

.

.

.

k

A_{i…k}

Ai…k​和

A

k

+

1…

j

A_{k+1…j}

Ak+1…j​已经是最优括号化。

Step2：递归解（递归地定义一个最优解的值）

对于矩阵链乘，子问题的最优解的值为：确定

A

i

.

.

.

j

A_{i…j}

Ai…j​括号化的最小代价（按最优括号化计算的成本）。

设

m

[

i

,

j

]

m[i,j]

m[i,j]（主角登场，数组

m

[

i

,

j

]

m[i,j]

m[i,j]非常重要）是计算

A

i

.

.

.

j

A_{i…j}

Ai…j​所需乘法的最小次数（最优解的值），则

A

1…

n

A_{1…n}

A1…n​的最小计算成本为

m

[

1

,

n

]

m[1,n]

m[1,n]。作如下规定：

  1. 若

    i

    =

    j

    i=j

    i=j，

    m

    [

    i

    ,

    j

    ]

    =

    0

    m[i,j]=0

    m[i,j]=0，链上只有一个

    A

    i

    A_i

    Ai​，无需乘法（矩阵乘法需要两个

    A

    i

    A_i

    Ai​和

    A

    j

    A_j

    Aj​才能完成，假定两个矩阵的维度是

    j

    ×

    k

    ,

    k

    ×

    l

    j\times{k},k\times{l}

    j×k,k×l，则矩阵乘法所需的运算次数就是

    j

    ×

    k

    ×

    l

    j\times{k}\times{l}

    j×k×l）；

  2. 若

    i

    < j i

    m

    [

    i

    ,

    j

    ]

    =

    0

    ,

    w

    h

    e

    n

      

    i

    =

    j

    m[i,j]=0, when\ \ i=j

    m[i,j]=0,when  i=j

    m

    [

    i

    ,

    j

    ]

    =

    min

    ⁡

    i

    ≤

    k

    < j { m [ i , k ] + m [ k + 1 , j ] + p i − 1 p k p j } , w h e n    i < j m[i,j]=\min_{i\leq{k}\lt{j}}\{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\}, when\ \ i\lt{j} m[i,j]=mini≤km[i,k]+m[k+1,j]+pi−1​pk​pj​},when  i

    如此可以得到最小成本，如果想要进一步构造最优解（指出矩阵链乘的分裂点在哪里，或者说最优括号化方案是什么）则还需要定义

    S

    [

    i

    ,

    j

    ]

    S[i,j]

    S[i,j]来记录分裂点k。

Step3：计算最优解的值

由于自顶向下使用递归计算最优解的过程中存在重叠子问题，因此使用自顶向上的方式进行计算，而这个自顶向上的计算方法，说穿了是一个填表的过程。

借用文章https://blog.csdn.net/qq_19782019/article/details/94356886当中的一个矩阵链乘的例子：

假定现在有4个矩阵

A

1

,

A

2

,

A

3

,

A

4

A_1, A_2, A_3, A_4

A1​,A2​,A3​,A4​组成的一个矩阵链，并且矩阵的规模序列为

< 5 , 4 , 6 , 2 , 7 >

<5, 4, 6, 2, 7>

<5,4,6,2,7>，求矩阵链的最优括号化方案。

需要注意的是，给定矩阵的规模序列为

p

=

< 5 , 4 , 6 , 2 , 7 >

p=<5, 4, 6, 2, 7>

p=<5,4,6,2,7>，意思就是矩阵链上包含着

∣

p

∣

−

1

=

4

|p|-1=4

∣p∣−1=4个矩阵，矩阵的维度依次为：

5

×

4

,

4

×

6

,

6

×

2

,

2

×

7

5\times4, 4\times6, 6\times2, 2\times7

5×4,4×6,6×2,2×7。

由于我们已知数组

m

m

m是一个上三角矩阵，如果想要构造最优括号化方案，即求出

m

[

1

,

4

]

m[1,4]

m[1,4]，并记录分裂点

k

k

k。因此初始化的数组m如下，由Step2得知，当

i

=

j

i=j

i=j时，

m

[

i

,

i

]

=

0

m[i,i]=0

m[i,i]=0，现在只要根据

i

< j i\lt{j} i

1 2 3 4
0 1
– 0 2
– – 0 3
– – – 0 4

首先求

m

[

1

,

2

]

,

m

[

2

,

3

]

,

m

[

3

,

4

]

m[1,2], m[2,3], m[3,4]

m[1,2],m[2,3],m[3,4]。仅仅拿

m

[

1

,

2

]

m[1,2]

m[1,2]为例：根据定义，显然

m

[

1

,

2

]

=

m

[

1

,

1

]

+

m

[

2

,

2

]

+

p

0

p

1

p

2

m[1,2]=m[1,1]+m[2,2]+p_{0}p_1p_2

m[1,2]=m[1,1]+m[2,2]+p0​p1​p2​，即只有两个矩阵相乘的情况，如实将两个矩阵进行乘法所需的计算次数填表即可。

m

[

1

,

2

]

=

5

×

4

×

6

=

120

,

m

[

2

,

3

]

=

4

×

6

×

2

=

48

,

m

[

3

,

4

]

=

6

×

2

×

7

=

84

m[1,2]=5\times4\times6=120, m[2,3]=4\times6\times2=48, m[3,4]=6\times2\times7=84

m[1,2]=5×4×6=120,m[2,3]=4×6×2=48,m[3,4]=6×2×7=84，更新表格，得到：

1 2 3 4
0 120 1
– 0 48 2
– – 0 84 3
– – – 0 4

我们还需要维护一张S表，它的作用是记录分裂点的位置：

1 2 3 4
0 1 1
– 0 2 2
– – 0 3 3
– – – 0 4

根据以上的分析，我们很显然可以看出，若

m

[

i

,

j

]

m[i,j]

m[i,j]中的

i

i

i和

j

j

j相邻，那么计算的结果就是两个矩阵的乘法，这一步是非常简单可以求得的。而进一步地维护

m

m

m表，现在需要求

m

[

1

,

3

]

m[1,3]

m[1,3]和

m

[

2

,

4

]

m[2,4]

m[2,4]，就没有那么容易了。

首先求

m

[

1

,

3

]

m[1,3]

m[1,3]，根据定义，

m

[

1

,

3

]

=

min

⁡

{

m

[

1

,

1

]

+

m

[

2

,

3

]

+

p

0

p

1

p

3

,

m

[

1

,

2

]

+

m

[

3

,

3

]

+

p

0

p

2

p

3

}

m[1,3]=\min\{m[1,1]+m[2,3]+p_{0}p_1p_3, m[1,2]+m[3,3]+p_0p_2p_3\}

m[1,3]=min{m[1,1]+m[2,3]+p0​p1​p3​,m[1,2]+m[3,3]+p0​p2​p3​}，

p

0

p

1

p

3

=

40

,

p

0

p

2

p

3

=

60

p_0p_1p_3=40, p_0p_2p_3=60

p0​p1​p3​=40,p0​p2​p3​=60，因此最小值是

m

[

1

,

3

]

=

min

⁡

{

48

+

40

,

60

+

120

}

=

88

m[1,3]=\min\{48+40, 60+120\}=88

m[1,3]=min{48+40,60+120}=88，分裂点

k

1

,

3

=

1

k_{1,3}=1

k1,3​=1；

再根据定义求

m

[

2

,

4

]

m[2,4]

m[2,4]，

m

[

2

,

4

]

=

min

⁡

{

m

[

2

,

2

]

+

m

[

3

,

4

]

+

p

1

p

2

p

4

,

m

[

2

,

3

]

+

m

[

4

,

4

]

+

p

1

p

3

p

4

}

m[2,4]=\min\{m[2,2]+m[3,4]+p_1p_2p_4, m[2,3]+m[4,4]+p_1p_3p_4\}

m[2,4]=min{m[2,2]+m[3,4]+p1​p2​p4​,m[2,3]+m[4,4]+p1​p3​p4​}，

p

1

p

2

p

4

=

168

,

p

1

p

3

p

4

=

56

p_1p_2p_4=168, p_1p_3p_4=56

p1​p2​p4​=168,p1​p3​p4​=56，故最小值是

m

[

2

,

4

]

=

104

m[2,4]=104

m[2,4]=104，分裂点

k

2

,

4

=

3

k_{2,4}=3

k2,4​=3。更新表格，有：

1 2 3 4
0 120 88 1
– 0 48 104 2
– – 0 84 3
– – – 0 4

进一步更新维护分裂点位置的

S

S

S表：

1 2 3 4
0 1 1 1
– 0 2 3 2
– – 0 3 3
– – – 0 4

最后求

m

[

1

,

4

]

m[1,4]

m[1,4]，

m

[

1

,

4

]

m[1,4]

m[1,4]的值就是答案：

m

[

1

,

4

]

=

min

⁡

{

m

[

1

,

1

]

+

m

[

2

,

4

]

+

p

0

p

1

p

4

,

m

[

1

,

2

]

+

m

[

3

,

4

]

+

p

0

p

2

p

4

,

m

[

1

,

3

]

+

m

[

4

,

4

]

+

p

0

p

3

p

4

}

m[1,4]=\min\{m[1,1]+m[2,4]+p_0p_1p_4, m[1,2]+m[3,4]+p_0p_2p_4, m[1,3]+m[4,4]+p_0p_3p_4\}

m[1,4]=min{m[1,1]+m[2,4]+p0​p1​p4​,m[1,2]+m[3,4]+p0​p2​p4​,m[1,3]+m[4,4]+p0​p3​p4​}，其中

p

0

p

1

p

4

=

140

,

p

0

p

2

p

4

=

210

,

p

0

p

3

p

4

=

70

p_0p_1p_4=140, p_0p_2p_4=210, p_0p_3p_4=70

p0​p1​p4​=140,p0​p2​p4​=210,p0​p3​p4​=70，故最终的答案为

m

[

1

,

4

]

=

min

⁡

{

104

+

140

=

244

,

120

+

84

+

210

=

414

,

88

+

70

=

158

}

=

158

m[1,4]=\min\{104+140=244, 120+84+210=414, 88+70=158\}=158

m[1,4]=min{104+140=244,120+84+210=414,88+70=158}=158，分裂点

k

1

,

4

=

3

k_{1,4}=3

k1,4​=3。

得到最终的两张表，第一张为

m

m

m表，第二张为

S

S

S表：

1 2 3 4
0 120 88 158 1
– 0 48 104 2
– – 0 84 3
– – – 0 4
1 2 3 4
0 1 1 3 1
– 0 2 3 2
– – 0 3 3
– – – 0 4

Step4：构造一个最优解

由于

S

[

i

,

j

]

=

k

S[i,j]=k

S[i,j]=k记录了

A

i

.

.

.

j

A_{i…j}

Ai…j​最优括号化的分裂点k，设

k

1

=

S

[

1

,

n

]

k_1=S[1,n]

k1​=S[1,n]，则

A

1…

n

A_{1…n}

A1…n​的计算次序是

A

1…

k

1

⋅

A

k

1

+

1…

n

A_{1…k_1}\cdot{A_{k_1+1…n}}

A1…k1​​⋅Ak1​+1…n​，而

A

1…

k

1

A_{1…k_1}

A1…k1​​的计算次序（分裂点）记录在

S

[

1

,

k

1

]

S[1,k_1]

S[1,k1​]当中，不妨令

k

2

=

S

[

1

,

k

1

]

k_2=S[1,k_1]

k2​=S[1,k1​]，其计算次序为

A

1…

k

2

⋅

A

k

2

+

1…

k

1

A_{1…k_2}\cdot{A_{k_2+1…k_1}}

A1…k2​​⋅Ak2​+1…k1​​。

由此，针对上述例题：矩阵链乘的最少计算次数为

m

[

1

,

4

]

=

158

m[1,4]=158

m[1,4]=158，而最优括号化方案为

A

1

(

A

2

A

3

)

A

4

A_1(A_2A_3)A_4

A1​(A2​A3​)A4​

Longest Common Subsequence

两个序列的公共子序列（LCS）： 若Z是X的子列，又是Y的子列，则Z是序列X和Y的公共子序列。而最长公共子序列即X和Y的公共子序列中长度最长者。

Step1：刻画LCS的结构特征（描述最优子结构）

设

X

=

< x 1 , x 2 , . . . , x m >

X=

X=和

Y

=

< y 1 , y 2 , . . . , y n >

Y=

Y=是序列，

Z

=

< z 1 , z 2 , . . . , z k >

Z=

Z=是X和Y的任意一个LCS，有：

  1. 若

    x

    m

    =

    y

    n

    x_m=y_n

    xm​=yn​，则

    z

    k

    =

    x

    m

    =

    y

    n

    z_k=x_m=y_n

    zk​=xm​=yn​且

    Z

    k

    −

    1

    Z_{k-1}

    Zk−1​是

    X

    m

    −

    1

    X_{m-1}

    Xm−1​和

    Y

    n

    −

    1

    Y_{n-1}

    Yn−1​的一个LCS；

  2. 若

    x

    m

    ≠

    y

    n

    x_m\neq{y_n}

    xm​=yn​，且

    z

    k

    ≠

    x

    m

    z_k\neq{x_m}

    zk​=xm​，则Z是

    X

    m

    −

    1

    X_{m-1}

    Xm−1​和Y的一个LCS；

  3. 若

    x

    m

    ≠

    y

    n

    x_m\neq{y_n}

    xm​=yn​，且

    z

    k

    ≠

    y

    n

    z_k\neq{y_n}

    zk​=yn​，则Z是X和

    Y

    n

    −

    1

    Y_{n-1}

    Yn−1​的一个LCS；

上述成立的定理非常重要，可以使用反证法证明。该定理表明LCS问题具有“最优子结构”性质：两个序列的一个LCS包含了两个序列的前缀子序列的一个LCS。

蕴含的选择：当

x

m

≠

y

n

x_m\neq{y_n}

xm​=yn​时，即两个序列的后缀不对齐，我们事先并不知道

Z

Z

Z的长度，只能在

X

m

−

1

X_{m-1}

Xm−1​和

Y

Y

Y的LCS以及在

X

X

X和

Y

n

−

1

Y_{n-1}

Yn−1​的LCS中取最大者。👈这个assertion给出了构造递归式的方法。

Step2：子问题的递归解

寻找

X

X

X和

Y

Y

Y的一个LCS，可以分解为1个或2个子问题：

  1. 如果

    x

    m

    =

    y

    n

    x_m=y_n

    xm​=yn​，需求解一个子问题，即寻找

    X

    m

    −

    1

    X_{m-1}

    Xm−1​和

    Y

    n

    −

    1

    Y_{n-1}

    Yn−1​的1个LCS；

  2. 如果

    x

    m

    ≠

    y

    n

    x_m\neq{y_n}

    xm​=yn​，则需要求解两个子问题：寻找

    X

    m

    −

    1

    X_{m-1}

    Xm−1​和

    Y

    Y

    Y的1个LCS或是寻找

    X

    X

    X个

    Y

    n

    −

    1

    Y_{n-1}

    Yn−1​的一个LCS，由于主问题是寻找最长的LCS，因此取二者中最长者。

由此产生了一张非常重要的表格，即表格

C

C

C。使用

C

C

C来记录最优解的值，它有如下定义：

C

[

i

,

j

]

C[i,j]

C[i,j]定义为

X

i

X_i

Xi​和

Y

j

Y_j

Yj​的一个LCS长度，进而有：

C

[

i

,

j

]

=

0

，如果

i

=

0

或

j

=

0

或

X

和

Y

有一个为空序列，此时

L

C

S

长度为

0

C[i,j]=0，如果i=0或j=0或X和Y有一个为空序列，此时LCS长度为0

C[i,j]=0，如果i=0或j=0或X和Y有一个为空序列，此时LCS长度为0；

C

[

i

,

j

]

=

C

[

i

−

1

,

j

−

1

]

+

1

，如果

i

>

j

并且

x

i

=

x

j

C[i,j]=C[i-1,j-1]+1，如果i\gt{j}并且x_i=x_j

C[i,j]=C[i−1,j−1]+1，如果i>j并且xi​=xj​；

C

[

i

,

j

]

=

max

⁡

{

C

[

i

,

j

−

1

]

,

C

[

i

−

1

,

j

]

}

，如果

i

,

j

>

0

且

x

i

≠

y

j

C[i,j]=\max\{C[i,j-1],C[i-1,j]\}，如果i,j\gt0且x_i\neq{y_j}

C[i,j]=max{C[i,j−1],C[i−1,j]}，如果i,j>0且xi​=yj​。

👆如果单纯地使用递归式来对LCS进行求解，会产生大量的重叠子问题，使用记忆化搜索（即LCS的备忘录版本）可以解决这个问题，但还可以使用自底向上的方式进行求解。

Step3：计算最优解

  • 输入：

    X

    =

    < x 1 , x 2 , . . . , x m >

    ,

    Y

    =

    < y 1 , y 2 , . . . , y n >

    X=, Y=

    X=,Y=；

  • 输出：

    C

    [

    0…

    m

    ,

    0…

    n

    ]

    C[0…m, 0…n]

    C[0…m,0…n]——计算次序行主序；

    b

    [

    1…

    m

    ,

    1…

    n

    ]

    b[1…m,1…n]

    b[1…m,1…n]——解矩阵（空串无需表示出解）

    b

    [

    i

    ,

    j

    ]

    =

    ↖

    ，如果

    C

    [

    i

    ,

    j

    ]

    由

    C

    [

    i

    −

    1

    ,

    j

    −

    1

    ]

    确定

    b[i,j]=\nwarrow，如果C[i,j]由C[i-1,j-1]确定

    b[i,j]=↖，如果C[i,j]由C[i−1,j−1]确定；

    b

    [

    i

    ,

    j

    ]

    =

    ↑

    ，如果

    C

    [

    i

    ,

    j

    ]

    由

    C

    [

    i

    −

    1

    ,

    j

    ]

    确定

    b[i,j]=\uparrow，如果C[i,j]由C[i-1,j]确定

    b[i,j]=↑，如果C[i,j]由C[i−1,j]确定；

    b

    [

    i

    ,

    j

    ]

    =

    ←

    ，如果

    C

    [

    i

    ,

    j

    ]

    由

    C

    [

    i

    ,

    j

    −

    1

    ]

    确定

    b[i,j]=\leftarrow，如果C[i,j]由C[i,j-1]确定

    b[i,j]=←，如果C[i,j]由C[i,j−1]确定；

当构造解时，从

b

[

m

,

n

]

b[m,n]

b[m,n]出发，回溯至

i

=

0

或

j

=

0

i=0或j=0

i=0或j=0时为止，当遇到

b

[

i

,

j

]

=

↖

b[i,j]=\nwarrow

b[i,j]=↖时，打印出

x

i

x_i

xi​即可。

Step4：构造LCS

从

b

[

m

,

n

]

b[m,n]

b[m,n]开始据箭头回溯至

i

=

0

或

j

=

0

i=0或j=0

i=0或j=0即可。当

b

[

i

,

j

]

=

↖

b[i,j]=\nwarrow

b[i,j]=↖时，有

x

i

=

y

j

x_i=y_j

xi​=yj​，打印之。

DP求解LCS的一个填表的例子1

借用文章https://blog.csdn.net/vangoudan/article/details/106388877当中的例子：

输入为：

X

=

{

A

,

C

,

A

,

B

,

D

,

F

}

,

Y

=

{

B

,

C

,

A

,

D

,

G

,

F

}

X=\{A,C,A,B,D,F\}, Y=\{B,C,A,D,G,F\}

X={A,C,A,B,D,F},Y={B,C,A,D,G,F}，求解二者的LCS；

采用填表的方式，表中填写的数据包括两个，即同时填写

C

[

i

,

j

]

C[i,j]

C[i,j]以及该位置对应的

b

(

↖

/

↑

/

←

)

b(\nwarrow/\uparrow/\leftarrow)

b(↖/↑/←)。

下面开始填表：

A C A B D F
0 0 0 0 0 0 0
B 0 0 0 0 1

↖

\nwarrow

↖

00
C001

↖

\nwarrow

↖

1

←

\leftarrow

←

1

←

\leftarrow

←

2

↖

\nwarrow

↖

1

←

\leftarrow

←

A01

↖

\nwarrow

↖

1

←

\leftarrow

←

2

↖

\nwarrow

↖

2

←

\leftarrow

←

2

←

\leftarrow

←

2

←

\leftarrow

←

D01

↑

\uparrow

↑

1

←

\leftarrow

←

2

↑

\uparrow

↑

2

←

\leftarrow

←

3

↖

\nwarrow

↖

3

←

\leftarrow

←

G01

↑

\uparrow

↑

1

←

\leftarrow

←

2

↑

\uparrow

↑

2

←

\leftarrow

←

3

↑

\uparrow

↑

3

←

\leftarrow

←

F01

↑

\uparrow

↑

1

←

\leftarrow

←

2

↑

\uparrow

↑

2

←

\leftarrow

←

3

↑

\uparrow

↑

4

↖

\nwarrow

↖

根据表格中的箭头指向，有：

在这里插入图片描述

因此LCS是

C

A

D

F

CADF

CADF。

DP求解LCS的一个填表的例子2

同样来自文章https://blog.csdn.net/vangoudan/article/details/106388877当中的例子：

输入为：

X

=

{

A

,

B

,

C

,

B

,

D

,

A

,

B

}

,

Y

=

{

B

,

D

,

C

,

A

,

B

,

A

}

X=\{A,B,C,B,D,A,B\}, Y=\{B,D,C,A,B,A\}

X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A}，求解二者的LCS；

采用填表的方式，表中填写的数据包括两个，即同时填写

C

[

i

,

j

]

C[i,j]

C[i,j]以及该位置对应的

b

(

↖

/

↑

/

←

)

b(\nwarrow/\uparrow/\leftarrow)

b(↖/↑/←)。

A B C B D A B
0 0 0 0 0 0 0 0
B 0 0 1

↖

\nwarrow

↖

1

←

\leftarrow

←

1

↖

\nwarrow

↖

1

←

\leftarrow

←

1

←

\leftarrow

←

1

↖

\nwarrow

↖

D001

↑

\uparrow

↑

1

←

\leftarrow

←

1

←

\leftarrow

←

2

↖

\nwarrow

↖

2

←

\leftarrow

←

2

←

\leftarrow

←

C001

↑

\uparrow

↑

2

↖

\nwarrow

↖

2

←

\leftarrow

←

2

←

\leftarrow

←

2

←

\leftarrow

←

2

←

\leftarrow

←

A01

↖

\nwarrow

↖

1

←

\leftarrow

←

2

↑

\uparrow

↑

2

←

\leftarrow

←

2

←

\leftarrow

←

3

↖

\nwarrow

↖

3

←

\leftarrow

←

B01

↑

\uparrow

↑

2

↖

\nwarrow

↖

2

←

\leftarrow

←

3

↖

\nwarrow

↖

3

←

\leftarrow

←

3

←

\leftarrow

←

4

↖

\nwarrow

↖

A01

↖

\nwarrow

↖

2

↑

\uparrow

↑

2

←

\leftarrow

←

3

↑

\uparrow

↑

3

←

\leftarrow

←

4

↖

\nwarrow

↖

4

←

\leftarrow

←

根据表格中的箭头，有：

在这里插入图片描述

显然，针对输入，

B

C

B

A

和

B

C

A

B

BCBA和BCAB

BCBA和BCAB均是满足条件的LCS，输出其一即可。

算法导论当中的例子：15.4-1

题目描述： 求

< 1 , 0 , 0 , 1 , 0 , 1 , 0 , 1 >

<1,0,0,1,0,1,0,1>

<1,0,0,1,0,1,0,1>和

< 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 0 >

<0,1,0,1,1,0,1,1,0>

<0,1,0,1,1,0,1,1,0>的一个LCS。

同样采用画表的方式进行求解：

1 0 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0
0 0 0 1

↖

\nwarrow

↖

1

↖

\nwarrow

↖

1

←

\leftarrow

←

1

↖

\nwarrow

↖

1

←

\leftarrow

←

1

↖

\nwarrow

↖

1

←

\leftarrow

←

101

↖

\nwarrow

↖

1

←

\leftarrow

←

1

←

\leftarrow

←

2

↖

\nwarrow

↖

2

←

\leftarrow

←

2

↖

\nwarrow

↖

2

←

\leftarrow

←

2

↖

\nwarrow

↖

001

↑

\uparrow

↑

2

↖

\nwarrow

↖

2

↖

\nwarrow

↖

2

←

\leftarrow

←

3

↖

\nwarrow

↖

3

←

\leftarrow

←

3

↖

\nwarrow

↖

3

←

\leftarrow

←

101

↖

\nwarrow

↖

2

↑

\uparrow

↑

2

←

\leftarrow

←

3

↖

\nwarrow

↖

3

←

\leftarrow

←

4

↖

\nwarrow

↖

4

←

\leftarrow

←

4

↖

\nwarrow

↖

101

↖

\nwarrow

↖

2

↑

\uparrow

↑

2

←

\leftarrow

←

3

↖

\nwarrow

↖

3

←

\leftarrow

←

4

↖

\nwarrow

↖

4

←

\leftarrow

←

5

↖

\nwarrow

↖

001

↑

\uparrow

↑

2

↖

\nwarrow

↖

3

↖

\nwarrow

↖

3

←

\leftarrow

←

4

↖

\nwarrow

↖

4

←

\leftarrow

←

5

↖

\nwarrow

↖

5

←

\leftarrow

←

101

↖

\nwarrow

↖

2

↑

\uparrow

↑

3

↑

\uparrow

↑

4

↖

\nwarrow

↖

4

←

\leftarrow

←

5

↖

\nwarrow

↖

5

←

\leftarrow

←

6

↖

\nwarrow

↖

101

↖

\nwarrow

↖

2

↑

\uparrow

↑

3

↑

\uparrow

↑

4

↖

\nwarrow

↖

4

←

\leftarrow

←

5

↖

\nwarrow

↖

5

←

\leftarrow

←

6

↖

\nwarrow

↖

001

↑

\uparrow

↑

2

↖

\nwarrow

↖

3

↖

\nwarrow

↖

4

↑

\uparrow

↑

5

↖

\nwarrow

↖

5

←

\leftarrow

←

6

↖

\nwarrow

↖

6

←

\leftarrow

←

根据表格，得到：

在这里插入图片描述

因此，LCS为

100110

或

101011

100110或101011

100110或101011。

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/fba97c3774.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐