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> <A1,A2,...,An>,需要计算其矩阵乘积 A 1 A 2 . . . A n A_1A_2...A_n A1A2...An。
计算多个矩阵链乘的积可以使用括号来指定计算次序,每一个括号内的矩阵相乘调用标准的矩阵乘法。不同括号化方式产生不同的计算成本。 因此,矩阵链乘实质上是一个最优括号化问题。
用动态规划可以获得多项式解。
Step1:最优的括号化结构(描述最优解的结构性质)
- 将 A i A i + 1 . . . A j A_iA_{i+1}...A_j AiAi+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]。作如下规定:
- 若 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);
- 若
i
<
j
i<j
i<j,由Step1中的最优解结构可知,假定最优括号化的分裂点为k,则
m
[
i
,
j
]
=
m
[
i
,
k
]
+
m
[
k
+
1
,
j
]
+
p
i
−
1
⋅
p
k
⋅
p
j
m[i,j]=m[i,k]+m[k+1,j]+p_{i-1}\cdot{p_{k}}\cdot{p_{j}}
m[i,j]=m[i,k]+m[k+1,j]+pi−1⋅pk⋅pj。其中
m
[
i
,
k
]
m[i,k]
m[i,k]表示子积
A
i
.
.
.
k
A_{i...k}
Ai...k的代价,而
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的列。在不知道
k
k
k的取值时,应该在
j
−
i
j-i
j−i个值中选取最优者,即能够使矩阵链乘的计算次数最小者,所以
A
i
.
.
.
j
A_{i...j}
Ai...j的最小计算成本为:
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≤k<j{m[i,k]+m[k+1,j]+pi−1pkpj},when i<j
如此可以得到最小成本,如果想要进一步构造最优解(指出矩阵链乘的分裂点在哪里,或者说最优括号化方案是什么)则还需要定义 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<j时的递归式填写表格,并记录 S S S,即可得到最终的答案。
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]+p0p1p2,即只有两个矩阵相乘的情况,如实将两个矩阵进行乘法所需的计算次数填表即可。 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]+p0p1p3,m[1,2]+m[3,3]+p0p2p3}, p 0 p 1 p 3 = 40 , p 0 p 2 p 3 = 60 p_0p_1p_3=40, p_0p_2p_3=60 p0p1p3=40,p0p2p3=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]+p1p2p4,m[2,3]+m[4,4]+p1p3p4}, p 1 p 2 p 4 = 168 , p 1 p 3 p 4 = 56 p_1p_2p_4=168, p_1p_3p_4=56 p1p2p4=168,p1p3p4=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]+p0p1p4,m[1,2]+m[3,4]+p0p2p4,m[1,3]+m[4,4]+p0p3p4},其中
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
p0p1p4=140,p0p2p4=210,p0p3p4=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(A2A3)A4
Longest Common Subsequence
两个序列的公共子序列(LCS): 若Z是X的子列,又是Y的子列,则Z是序列X和Y的公共子序列。而最长公共子序列即X和Y的公共子序列中长度最长者。
Step1:刻画LCS的结构特征(描述最优子结构)
设 X = < x 1 , x 2 , . . . , x m > X=<x_1,x_2,...,x_m> X=<x1,x2,...,xm>和 Y = < y 1 , y 2 , . . . , y n > Y=<y_1,y_2,...,y_n> Y=<y1,y2,...,yn>是序列, Z = < z 1 , z 2 , . . . , z k > Z=<z_1,z_2,...,z_k> Z=<z1,z2,...,zk>是X和Y的任意一个LCS,有:
- 若 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;
- 若 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;
- 若 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个子问题:
- 如果 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;
- 如果 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=<x_1,x_2,...,x_m>, Y=<y_1,y_2,...,y_n> X=<x1,x2,...,xm>,Y=<y1,y2,...,yn>;
- 输出:
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 ↖ | 0 | 0 |
C | 0 | 0 | 1 ↖ \nwarrow ↖ | 1 ← \leftarrow ← | 1 ← \leftarrow ← | 2 ↖ \nwarrow ↖ | 1 ← \leftarrow ← |
A | 0 | 1 ↖ \nwarrow ↖ | 1 ← \leftarrow ← | 2 ↖ \nwarrow ↖ | 2 ← \leftarrow ← | 2 ← \leftarrow ← | 2 ← \leftarrow ← |
D | 0 | 1 ↑ \uparrow ↑ | 1 ← \leftarrow ← | 2 ↑ \uparrow ↑ | 2 ← \leftarrow ← | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← |
G | 0 | 1 ↑ \uparrow ↑ | 1 ← \leftarrow ← | 2 ↑ \uparrow ↑ | 2 ← \leftarrow ← | 3 ↑ \uparrow ↑ | 3 ← \leftarrow ← |
F | 0 | 1 ↑ \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 ↖ |
D | 0 | 0 | 1 ↑ \uparrow ↑ | 1 ← \leftarrow ← | 1 ← \leftarrow ← | 2 ↖ \nwarrow ↖ | 2 ← \leftarrow ← | 2 ← \leftarrow ← |
C | 0 | 0 | 1 ↑ \uparrow ↑ | 2 ↖ \nwarrow ↖ | 2 ← \leftarrow ← | 2 ← \leftarrow ← | 2 ← \leftarrow ← | 2 ← \leftarrow ← |
A | 0 | 1 ↖ \nwarrow ↖ | 1 ← \leftarrow ← | 2 ↑ \uparrow ↑ | 2 ← \leftarrow ← | 2 ← \leftarrow ← | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← |
B | 0 | 1 ↑ \uparrow ↑ | 2 ↖ \nwarrow ↖ | 2 ← \leftarrow ← | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← | 3 ← \leftarrow ← | 4 ↖ \nwarrow ↖ |
A | 0 | 1 ↖ \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。
同样采用画表的方式进行求解:文章来源:https://www.toymoban.com/news/detail-777623.html
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 ← |
1 | 0 | 1 ↖ \nwarrow ↖ | 1 ← \leftarrow ← | 1 ← \leftarrow ← | 2 ↖ \nwarrow ↖ | 2 ← \leftarrow ← | 2 ↖ \nwarrow ↖ | 2 ← \leftarrow ← | 2 ↖ \nwarrow ↖ |
0 | 0 | 1 ↑ \uparrow ↑ | 2 ↖ \nwarrow ↖ | 2 ↖ \nwarrow ↖ | 2 ← \leftarrow ← | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← |
1 | 0 | 1 ↖ \nwarrow ↖ | 2 ↑ \uparrow ↑ | 2 ← \leftarrow ← | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← | 4 ↖ \nwarrow ↖ | 4 ← \leftarrow ← | 4 ↖ \nwarrow ↖ |
1 | 0 | 1 ↖ \nwarrow ↖ | 2 ↑ \uparrow ↑ | 2 ← \leftarrow ← | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← | 4 ↖ \nwarrow ↖ | 4 ← \leftarrow ← | 5 ↖ \nwarrow ↖ |
0 | 0 | 1 ↑ \uparrow ↑ | 2 ↖ \nwarrow ↖ | 3 ↖ \nwarrow ↖ | 3 ← \leftarrow ← | 4 ↖ \nwarrow ↖ | 4 ← \leftarrow ← | 5 ↖ \nwarrow ↖ | 5 ← \leftarrow ← |
1 | 0 | 1 ↖ \nwarrow ↖ | 2 ↑ \uparrow ↑ | 3 ↑ \uparrow ↑ | 4 ↖ \nwarrow ↖ | 4 ← \leftarrow ← | 5 ↖ \nwarrow ↖ | 5 ← \leftarrow ← | 6 ↖ \nwarrow ↖ |
1 | 0 | 1 ↖ \nwarrow ↖ | 2 ↑ \uparrow ↑ | 3 ↑ \uparrow ↑ | 4 ↖ \nwarrow ↖ | 4 ← \leftarrow ← | 5 ↖ \nwarrow ↖ | 5 ← \leftarrow ← | 6 ↖ \nwarrow ↖ |
0 | 0 | 1 ↑ \uparrow ↑ | 2 ↖ \nwarrow ↖ | 3 ↖ \nwarrow ↖ | 4 ↑ \uparrow ↑ | 5 ↖ \nwarrow ↖ | 5 ← \leftarrow ← | 6 ↖ \nwarrow ↖ | 6 ← \leftarrow ← |
根据表格,得到:
因此,LCS为
100110
或
101011
100110或101011
100110或101011。文章来源地址https://www.toymoban.com/news/detail-777623.html
到了这里,关于【Chapter 5】Dynamic Programming(上)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!