Homework3

第一题

在构建 c 数组时，不再维护额外的 b 数组来记录方向。 在需要回溯寻找具体的最长公共子序列时，直接通过比较 c[i] [j]、c[i-1] [j] 和 c[i] [j-1] 的值来判断当前字符是否属于最长公共子序列，以及应该向哪个方向回溯。

伪代码

FUNCTION LCS(const string s1, const string s2):
    m = s1.size() // 获取字符串 s1 的长度
    n = s2.size() // 获取字符串 s2 的长度
    dp[m+1][n+1] // 初始化动态规划表
    for i from 1 to m:
        for j from 1 to n: 
            if s1[i-1] == s2[j-1]: // 如果当前字符相同
                dp[i][j] = dp[i-1][j-1] + 1 // 当前位置的 LCS 长度等于左上方的值加 1，表示找到了一个公共子序列字符
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])                 // 如果当前字符不同，当前位置的 LCS 长度取上方和左方的最大值，表示不考虑当前字符
        end for
    end for

    return dp[m][n] // 返回最终的最长公共子序列长度，位于动态规划表的右下角
END FUNCTION

第二题

为了计算矩阵连乘积

$$A_1A_2A_3A_4A_5A_6$$

的最小乘法次数，我们使用动态规划方法构造两个表格 (m[i,j]) 和 (s[i,j])。其中 (m[i,j]) 表示从矩阵

$$A_i到A_j$$

相乘的最小乘法次数，而 (s[i,j]) 记录了最优分割点。

详细计算过程

$$m[i, j]=\left\{\begin{array}{cc} 0 & i=j \\ \min _{i \leq k<j}\left\{m[i, k]+m[k+1, j]+p_{i-1} p_{k} p_{j}\right\} & i<j \end{array}\right.$$

1. 链长 l=2：

   • m[1,2]=30×35×15=15750
   • m[2,3]=35×15×5=2625
   • m[3,4]=15×5×10=750
   • m[4,5]=5×10×20=1000
   • m[5,6]=10×20×25=5000

2. 链长 l=3：

   1. 计算 m[1,3]

   子链 A1A2A3，维度为 30×35、35×15、15×5。
   可能的 k值：k=1 或 k=2。

   • 当 k=1：
     分割为 (A1)(A2A3)
     计算式：

     m[1,1]+m[2,3]+30×35×5=0+2625+5250=7875

   • 当 k=2：
     分割为 (A1A2)(A3)
     计算式：

     m[1,2]+m[3,3]+30×15×5=15750+0+2250=18000

   最小值：min⁡(7875,18000)=7875，分割点 s[1,3]=1。

   2. 计算 m[2,4]

   子链 A2A3A4，维度为 35×15、15×5、5×10。
   可能的 k值：k=2 或 k=3。

   • 当 k=2：
     分割为 (A2)(A3A4)
     计算式：

     m[2,2]+m[3,4]+35×15×10=0+750+5250=6000

   • 当 k=3：
     分割为 (A2A3)(A4)
     计算式：

     m[2,3]+m[4,4]+35×5×10=2625+0+1750=4375

   最小值：min⁡(6000,4375)=4375，分割点 s[2,4]=3。

   3. 计算 m[3,5]

   子链 A3A4A5，维度为 15×515×5、5×105×10、10×2010×20。
   可能的 k 值：k=3 或 k=4。

   • 当 k=3：
     分割为 (A3)(A4A5)
     计算式：

     m[3,3]+m[4,5]+15×5×20=0+1000+1500=2500

   • 当 k=4：
     分割为 (A3A4)(A5)
     计算式：

     m[3,4]+m[5,5]+15×10×20=750+0+3000=3750

   最小值：min⁡(2500,3750)=2500，分割点 s[3,5]=3。

   4. 计算 m[4,6]

   子链 A4A5A6，维度为 5×10、10×20、20×25。
   可能的 k 值：k=4或 k=5。

   • 当 k=4：
     分割为 (A4)(A5A6)
     计算式：

     m[4,4]+m[5,6]+5×10×25=0+5000+1250=6250

   • 当 k=5：
     分割为 (A4A5)(A6)
     计算式：

     m[4,5]+m[6,6]+5×20×25=1000+0+2500=3500

   最小值：min⁡(6250,3500)=3500，分割点 s[4,6]=5。

   • m[1,3]=min(7875,18000)=7875（s[1,3] =1）
   • m[2,4]=min(6000,4375)=4375 （s[2,4]=3）
   • m[3,5]=min(2500,3750)=2500 （s[3,5]=3）
   • m[4,6]=min(6250,3500)=3500 （s[4,6]=5）

   子问题	计算过程（所有可能的 k值）	最小值	分割点 s[i,j]
   m[1,3]	k=1:7875 k=2:18000	7875	1
   m[2,4]	k=2:6000 k=3:4375	4375	3
   m[3,5]	k=3:2500 k=4:3750	2500	3
   m[4,6]	k=4:6250 k=5:3500	3500	5

   同理可以计算其他数值:

3. 链长 l=4：

   • m[1,4]=min⁡(14875,21000,9375)=9375（s[1,4]=3）
   • m[2,5]=min⁡(13000,7125,11375)=7125（s[2,5]=3）
   • m[3,6]=min⁡(5375,9500,10000)=5375 （s[3,6]=3）

4. 链长 l=5：

   • m[1,5]=min⁡(28125,27250,11875,15375)=11875（s[1,5]=3）
   • m[2,6]=min⁡(18500,10500,18125,24625)=10500（s[2,6]=3）

5. 链长 l=6：

   • m[1,6]=min⁡(36750,32375,15125,21875,26875)=15125（s[1,6]=3）

最终结果

最小乘法次数为 15125，最优括号化方案为：(A1A2A3)(A4A5A6)

m[i,j] 表（最小乘法次数）

i\j	1	2	3	4	5	6
1	0	15750	7875	9375	11875	15125
2	-	0	2625	4375	7125	10500
3	-	-	0	750	2500	5375
4	-	-	-	0	1000	3500
5	-	-	-	-	0	5000
6	-	-	-	-	-	0

s[i,j] 表（分割点）

i\j	1	2	3	4	5	6
1	-	1	1	3	3	3
2	-	-	2	3	3	3
3	-	-	-	3	3	3
4	-	-	-	-	4	5
5	-	-	-	-	-	5
6	-	-	-	-	-	-

第三题

X {A,C,A,B,D,F}和Y

cpp实现c数组矩阵输出

#include <vector>
#include <iostream>

using namespace std;

void printDPMatrix(const vector<vector<int>>& dp, int m, int n) {
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int LCS(const string& s1, const string& s2) {
    int m = s1.size();
    int n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {  // 遍历s1中的每个字符
        for (int j = 1; j <= n; j++) {  // 遍历s2中的每个字符
            if (s1[i-1] == s2[j-1]) {  // 如果当前字符相同
                dp[i][j] = dp[i-1][j-1] + 1;  // LCS长度加1
            } else {
                // 如果当前字符不同，选择不包括当前字符的最长LCS
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    printDPMatrix(dp, m, n);
    return dp[m][n];
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << "Length of LCS: "<<"\n" << LCS(s1, s2) << endl;
    return 0;
}

c数组（长度表）

$$C[i, j]=\left\{\begin{array}{cc} 0 & i=0 \text { 或者 } j=0 \\ C[i-1, j-1]+1 & x_i=y_j \\ \max (C[i-1, j], C[i, j-1]) & x_i!=y_j \end{array}\right\}$$

j\i	0	1.A	2.C	3.A	4.B	5.D	6.F
0	0	0	0	0	0	0	0
1.B	0	0	0	1	1	1	1
2.C	0	0	1	1	1	1	1
3.A	0	0	1	2	2	2	2
4.D	0	1	1	2	2	2	2
5.G	0	1	1	2	3	3	3
6.F	0	1	1	2	3	3	4

b数组（方向表）

结合c数组，按照标准的算法步骤，当元素不同时，比较c[i-1,j]和c[i,j-1]，如果上方的值大于等于左方，则方向向上，否则向左。

c[i,j]的值可以通过上述的公式得出

​ 1.xi=yj，用↖

​ 2.xi != yj时，如果C[i-1,j]>=C[i,j]，用↑，否则用←。

​ 3.当i=1，j=1时，因为x1!=y1，所以C[1,1]=max(C[i-1,j]，C[i,j-1])=0；因为C[i-1,j]>=C[i,j]，用↑。

j\i	0	1.A	2.C	3.A	4.B	5.D	6.F
0	—	—	—	—	—	—	—
1.B	—	⬆️1	⬆️	↖️	⬅️	⬅️	⬅️
2.C	—	⬆️	↖️1	⬆️	⬆️	⬆️	⬆️
3.A	—	⬆️	⬆️	↖️1	⬅️1	⬅️	⬅️
4.D	—	↖️	⬆️	⬆️	⬆️	↖1	⬆️
5.G	—	⬆️	⬆️	⬆️	↖️	⬆️1	⬅️
6.F	—	⬆️	⬆️	⬆️	⬆️	⬆️	↖️1

LCS结果

• 起点：从右下角b[6][6]（↖）开始，匹配F，加入LCS，移动至i=5, j=5。
• i=5, j=5：方向⬆️，左移至j=4，此时b[5][4]为↖，匹配D，加入LCS，移动至i=4, j=3。
• i=4, j=3：方向⬅️，上移至i=3，此时b[3][3]为↖，匹配A，加入LCS，移动至i=2, j=2。
• i=2, j=2：方向↖，匹配C，加入LCS，移动至i=1, j=1。
• i=1, j=1：方向⬆️，回溯结束。

收集的LCS（逆序）：F → D → A → C → 反转后 → C A D F，长度为4。