你好，同学。今天我们要挑战的这道题是 P1140 相似基因。

这道题是你在“编辑距离”和“最长公共子序列”之后，必须掌握的序列比对（Sequence Alignment）类 DP 的进阶模型。它不仅考察你对“状态来源”的判断，还通过一个“打分矩阵”考察你对权值转移和初始化边界的理解。

---

题目背景

大家都知道，基因可以看作一个碱基对序列。它包含了 $4$ 种核苷酸，简记作 A, C, G, T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。

在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。

题目描述

两个基因的相似度的计算方法如下：

对于两个已知基因，例如 AGTGATG 和 GTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基 -，例如：

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|} \hline \tt A & \tt G & \tt T & \tt G & \tt A & \tt T & \texttt - & \tt G \\ \hline \texttt - & \tt G & \tt T & \texttt - & \texttt - & \tt T & \texttt A & \tt G \\ \hline \end{array} $$

这样，两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：

$$\def\arraystretch{1.5} \begin{array}{ |c|c|c|c|c|c|} \hline & \tt A & \tt C & \tt G & \tt T & \texttt - \\ \hline \tt A & 5 & -1 & -2 & -1 & -3\\ \hline \tt C & -1 & 5 & -3 & -2 & -4 \\\hline \tt G & -2 & -3 & 5 & -2 & -2 \\\hline \tt T & -1 & -2 & -2 & 5 & -1 \\\hline \texttt - & -3 & -4 & -2 & -1 & * \\\hline \end{array} $$

那么相似度就是：$(-3)+5+5+(-2)+(-3)+5+(-3)+5=9$。因为两个基因的对应方法不唯一，例如又有：

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|} \hline \tt A & \tt G & \tt T & \tt G & \tt A & \tt T & \tt G \\ \hline \texttt - & \tt G & \tt T & \texttt T & \texttt A & \texttt - & \tt G \\ \hline \end{array} $$

相似度为：$(-3)+5+5+(-2)+5+(-1)+5=14$。规定两个基因的相似度为所有对应方法中，相似度最大的那个。

输入格式

共两行。每行首先是一个整数 $n$，表示基因序列的长度；隔一个空格后是一个基因序列，序列中只含 $\verb!A!,\verb!C!,\verb!G!,\verb!T!$ 四种字母。$1 \le n\le 100$。

输出格式

仅一行，即输入基因的相似度。

7 AGTGATG
5 GTTAG

14

---

你好，同学。今天我们要挑战的这道题是 P1140 相似基因。

这道题是你在“编辑距离”和“最长公共子序列”之后，必须掌握的序列比对（Sequence Alignment）类 DP 的进阶模型。它不仅考察你对“状态来源”的判断，还通过一个“打分矩阵”考察你对权值转移和初始化边界的理解。

---

第二部分：预备知识点

1. 二维 DP 状态定义：理解 dp[i][j] 为序列 A 前 $i$ 个字符与序列 B 前 $j$ 个字符匹配时的最大得分。
2. 打分矩阵映射：如何将字符（A, C, G, T, -）映射为数组下标以便快速查表。
3. 负权值初始化：由于打分矩阵中存在大量负数，dp 数组初值不能简单设为 0。
4. 多来源决策：理解“左、上、左上”分别代表的物理意义（A 匹配空、B 匹配空、AB 互相匹配）。

---

第三部分：启发式思维引导（草稿纸上的推理）

请拿出一张草稿纸，跟教练一起完成以下推理过程：

1. 建立打分查表

思考：代码里写一堆 if-else 判断碱基类型太慢且易错。 行动：在草稿纸上画一个 5x5 的数组 score[5][5]。

• 令 A=0, C=1, G=2, T=3, -=4。
• 将题目中的表格填进去。例如 score[0][4] = -3（表示 A 对应空碱基）。

2. 状态转移来源的“物理意义”

当你站在 dp[i][j] 这个格子里，你面前有三条路：

1. 左上方 ↘️：$A[i]$ 和 $B[j]$ 强行配对。
   • 消耗 A 一个字符，消耗 B 一个字符。
   • 得分：dp[i-1][j-1] + score(A[i], B[j])。
2. 上方 ⬇️：$A[i]$ 对应一个空碱基 -。
   • 消耗 A 一个字符，B 进度不变。
   • 得分：dp[i-1][j] + score(A[i], '-')。
3. 左方 ➡️：$B[j]$ 对应一个空碱基 -。
   • 消耗 B 一个字符，A 进度不变。
   • 得分：dp[i][j-1] + score('-', B[j])。

3. 边界初始化的陷阱

提问：如果 A 序列有 5 个字符，B 是空的，得分是多少？ 错误想法：dp[5][0] = 0。 正确推理：这相当于 A 的 5 个字符全部对应空碱基 -。 行动：dp[i][0] = dp[i-1][0] + score(A[i], '-')。第一行和第一列必须这样累加初始化。

---

第四部分：逻辑流程图 (Mermaid)

graph TD
    Start("开始 (Standard C++14)") --> MapTable("构建 score_5_5 打分矩阵")
    MapTable --> ReadData("读取两组序列 A 和 B")
    ReadData --> InitDP("初始化 dp 数组为极小负数")
    
    subgraph Boundary ["边界处理 (重要)"]
        ZeroZero("dp_0_0 = 0")
        InitCol("循环 i: dp_i_0 = dp_i-1_0 + score(A_i, '-')")
        InitRow("循环 j: dp_0_j = dp_0_j-1 + score('-', B_j)")
    end

    InitDP --> ZeroZero
    ZeroZero --> InitCol
    InitCol --> InitRow
    
    subgraph Transition ["二维 DP 状态转移"]
        OuterLoop("外层循环 i 从 1 到 n")
        InnerLoop("内层循环 j 从 1 到 m")
        GetScores("获取三种情况得分")
        Choice1("Case1: dp_i-1_j-1 + score(A_i, B_j)")
        Choice2("Case2: dp_i-1_j + score(A_i, '-')")
        Choice3("Case3: dp_i_j-1 + score('-', B_j)")
        CalcMax("dp_i_j = max(Case1, Case2, Case3)")
    end

    InitRow --> OuterLoop
    OuterLoop --> InnerLoop
    InnerLoop --> GetScores
    GetScores --> Choice1
    GetScores --> Choice2
    GetScores --> Choice3
    Choice1 --> CalcMax
    Choice2 --> CalcMax
    Choice3 --> CalcMax
    
    CalcMax --> NextJ("j 循环结束?")
    NextJ -- "否" --> InnerLoop
    NextJ -- "是" --> NextI("i 循环结束?")
    NextI -- "否" --> OuterLoop
    NextI -- "是" --> Output("输出 dp_n_m")
    
    Output --> End("结束")

---

第五部分：读题关键词与复杂度分析

1. 读题关键词

• “最大值”：提示使用 DP。
• “加入空碱基”：说明序列长度可以灵活变动，是典型的线性序列对齐模型。
• “对应方法不唯一”：存在重叠子问题，需要记录中间状态。

2. 时间复杂度分析

• 过程：双重嵌套循环填表，每个状态转移是 $O(1)$。
• 复杂度：$O(n \times m)$，其中 $n, m \le 100$。
• 思考：计算次数仅 $10^4$，对于 $1.0\text{s}$ 的时限来说，这道题的性能压力极小。

3. 空间复杂度分析

• 过程：需要一个 dp[105][105] 的数组。
• 内存占用：约 $100^2 \times 4 \text{ bytes} \approx 40 \text{ KB}$，远小于 $128 \text{MB}$。
• 优化建议：如果 $n, m$ 达到 $10^5$，则需要考虑滚动数组优化，但在 $n=100$ 时，优先保证代码可读性。

教练寄语： 这道题和编辑距离唯一的不同在于：每一个格子都要从三个方向转移过来（因为无论字符是否相等，你都可以选择给其中一个序列加空位）。你之前的错误是漏掉了其中一个方向或加错了权值，请在写代码时，脑子里始终刻画那个 2D 表格的三个箭头！加油！