【Chapter 5】Dynamic Programming(上)

这篇具有很好参考价值的文章主要介绍了【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> <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} 1ijn
  • 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} ikj1
  • 对于某个 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} pi1pkpj,其中 p i − 1 p_{i-1} pi1是矩阵 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<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]+pi1pkpj。其中 m [ i , k ] m[i,k] m[i,k]表示子积 A i . . . k A_{i...k} Ai...k的代价,而 p i − 1 p_{i-1} pi1表示矩阵 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 ji个值中选取最优者,即能够使矩阵链乘的计算次数最小者,所以 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]=minik<j{m[i,k]+m[k+1,j]+pi1pkpj},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 p1=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...k1Ak1+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...k2Ak2+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,有:

  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} Zk1 X m − 1 X_{m-1} Xm1 Y n − 1 Y_{n-1} Yn1的一个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} Xm1和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} Yn1的一个LCS;

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

蕴含的选择:当 x m ≠ y n x_m\neq{y_n} xm=yn时,即两个序列的后缀不对齐,我们事先并不知道 Z Z Z的长度,只能在 X m − 1 X_{m-1} Xm1 Y Y Y的LCS以及在 X X X Y n − 1 Y_{n-1} Yn1的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} Xm1 Y n − 1 Y_{n-1} Yn1的1个LCS;
  2. 如果 x m ≠ y n x_m\neq{y_n} xm=yn,则需要求解两个子问题:寻找 X m − 1 X_{m-1} Xm1 Y Y Y的1个LCS或是寻找 X X X Y n − 1 Y_{n-1} Yn1的一个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=0j=0XY有一个为空序列,此时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[i1,j1]+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,j1],C[i1,j]},如果i,j>0xi=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[i1,j1]确定
    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[i1,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,j1]确定

当构造解时,从 b [ m , n ] b[m,n] b[m,n]出发,回溯至 i = 0 或 j = 0 i=0或j=0 i=0j=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=0j=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

根据表格中的箭头指向,有:
【Chapter 5】Dynamic Programming(上),算法设计与分析,动态规划,算法
因此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

根据表格中的箭头,有:
【Chapter 5】Dynamic Programming(上),算法设计与分析,动态规划,算法
显然,针对输入, B C B A 和 B C A B BCBA和BCAB BCBABCAB均是满足条件的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
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

根据表格,得到:
【Chapter 5】Dynamic Programming(上),算法设计与分析,动态规划,算法
因此,LCS为 100110 或 101011 100110或101011 100110101011文章来源地址https://www.toymoban.com/news/detail-777623.html

到了这里,关于【Chapter 5】Dynamic Programming(上)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划Dynamic Programming

     上篇文章我们简单入门了动态规划(一般都是简单的上楼梯,分析数据等问题)点我跳转,今天给大家带来的是路径问题,相对于上一篇在一维中摸爬滚打,这次就要上升到二维解决问题,但都用的是动态规划思想嘛,所以大差不差,且听我慢慢道来。 还是用一样的方法,

    2024年03月27日
    浏览(49)
  • 动态规划(Dynamic Programming)详解

    引言: 动态规划(Dynamic Programming,简称DP)是计算机科学与数学领域中的一个经典算法设计策略,用于解决具有重叠子问题和最优子结构特性的复杂问题。它通过将问题分解为更小的子问题来避免重复计算,从而提高效率。本文旨在详细介绍动态规划的基本概念、原理、实现

    2024年04月13日
    浏览(38)
  • 浅析动态规划(Dynamic Programming,DP)

    动态规划可以理解为递归,只不过递归是通过函数实现,动态规划通过循环实现! 动态规划有多好用我就不过多介绍,写这篇文章的时候我也不是熟练掌握,只是单纯记录一下我的学习经历并分享一些我的心得体会,仅此而已。 推荐看一下这个视频,对你的理解应该会有所

    2024年04月27日
    浏览(39)
  • 【数据结构】动态规划(Dynamic Programming)

    求解决策过程(decision process)最优化的数学方法。 将多阶段决策过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。 与分治法类似,将待求解问题 分解成若干个子问题 。 但是经分解得到的子问题往往 不是相互独立 的。 如果使用分治法求解问题,有些子问

    2024年02月03日
    浏览(42)
  • Dynamic-Programming(动态规划)最细解题思路+代码详解(1)

    案例二:二维数组的 DP 我做了几十道 DP 的算法题,可以说,80% 的题,都是要用二维数组的,所以下面的题主要以二维数组为主,当然有人可能会说,要用一维还是二维,我怎么知道?这个问题不大,接着往下看。 问题描述 一个机器人位于一个 m x n 网格的左上角 (起始点在

    2024年04月26日
    浏览(37)
  • 【Chapter 5】Dynamic Programming(上)

    考前最后一节课明确提到这一部分会考矩阵链乘问题(Matrix Chain)或是最长公共子序列问题(Longest Common Subsequence, LCS),考察的形式是填写DP的Table,因此以blog的方式对复习的过程进行记录,并查缺补漏。 问题描述: 给定 n n n 个矩阵的序列 A 1 , A 2 , . . . , A n A_1, A_2, ..., A_

    2024年02月03日
    浏览(47)
  • Dynamic-Programming(动态规划)最细解题思路+代码详解,Android布局优化之include、merge、ViewStub的使用

    dp[0…m-1] [0] = 1; // 相当于最左面一列,机器人只能一直往下走 撸代码 三个步骤都写出来了,直接看代码 public static int uniquePaths(int m, int n) { if (m = 0 || n = 0) { return 0; } int[][] dp = new int[m][n]; // // 初始化 for(int i = 0; i m; i++){ dp[i][0] = 1; } for(int i = 0; i n; i++){ dp[0][i] = 1; } // 推导出 d

    2024年04月26日
    浏览(39)
  • 《算法通关之路》-chapter9动态规划

    《算法通关之路》学习笔记,记录一下自己的刷题过程,详细的内容请大家购买作者的书籍查阅。 爬楼梯 力扣第70题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 打家劫舍 力扣第198题 你是一个专业的

    2024年02月07日
    浏览(45)
  • 算法分析与设计--动态规划

    一、动态规划简介 二、动态规划求解步骤 三、动态规划典型应用 数字三角形问题 最大子段和问题 0-1背包问题 四、最长公共子序列问题 动态规划求解 五、总结 算法语言--java语言 动态规划算法通常用于求解具有某种最优性质的问题。动态规划与分治算法类似,其基本思想也

    2024年02月07日
    浏览(67)
  • 算法分析与设计---分治+动态规划

    1.分治法 适用条件: 问题规模缩小到一定程度容易求解 问题可以分解为若干个规模较小的 相同 子问题,即问题具有最优子结构( 使用分治法前提 ) 可以利用子问题的解合并为该问题的解( 决定是否使用分治法 ) 各个子问题 相互独立 ,即子问题之间不包含公共子问题(

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包