DNA序列还原


# 问题描述

给定一段受损的 DNA 碱基序列 dna1，在每次只操作一个碱基的情况下，将其以最少的操作步骤将其还原到未受损的 DNA 碱基序列 dna2。

只可以对 DNA 碱基序列中的一个碱基进行三种操作：
1. 增加一个碱基
2. 去除一个碱基
3. 替换一个碱基

## 输入描述:

输入两段 DNA 碱基序列，每段分一行输入

第一行为第一段受损的 DNA 碱基序列 dna1

第二行为第二段未受损的 DNA 碱基序列 dna2

## 输出描述:

最小操作步骤数

**备注**:

0 <= dna1.length, dna2.length <= 500

dna1 和 dna2 由大写英文字母 A、G、C、T 组成

**示例 1**

**输入**

AGCTTAGC

AGCTAGCT

**输出**

2

**说明**

AGCTTAGC -> AGCTAGC（删除 T）

AGCTAGC -> AGCTAGCT（增加 T）


**示例 2**

**输入**

AGCCGAGC

GCTAGCT

**输出**

4

**说明**

AGCCGAGC -> GCCGAGC（删除 A）

GCCGAGC -> GCTGAGC（将 C 替换为 T）

GCTGAGC -> GCTAGC（删除 G）

GCTAGC -> GCTAGCT（增加 T）

解法：

解题思路

这个问题可以用动态规划来解决。我们定义一个二维数组dp[i][j]，表示将dna1的前i个字符转换为dna2的前j个字符所需要的最小编辑距离。

算法流程

先找到状态转移方程：


dp[i][j] = min(dp[i-1][j] + 1,  // 删除操作
               dp[i][j-1] + 1,  // 插入操作
               dp[i-1][j-1] + cost) // 替换操作

那么这个状态转移方程是怎么得来的呢？拿示例1来举例：

dna1：AGCTTAGC dna2：AGCTAGCT

假设坐标从1开始，那么 dp[8][8] 可以这么得来：

假设已经得到dna1前7个序列变成dna2前8个序列的最小操作距离dp[7][8]，现在dna1前7个序列后面多了碱基序列C，那么就需要在dp[7][8]的基础上再加一步把这个C删除，即：


AGCTTAG_ -> AGCTAGCT  假设得到最小操作距离为 dp[7][8]
AGCTTAGC -> AGCTAGCT  方法之一是先对前7个序列操作变成目标序列，
											现在多了最后的C，所以多一步删除操作，dp[7][8] + 1

假设已经得到dna1前8个序列变成dna2前7个序列的最小操作距离dp[8][7]，现在dna2前7个序列后面多了碱基序列T，那么需要在dp[8][7]的基础上再加一步把这个T插入，即：


AGCTTAGC -> AGCTAGC_  假设得到最小操作距离为 dp[8][7]
AGCTTAGC -> AGCTAGCT  方法之一是先对前8个序列操作变成目标序列的前7个序列，
											现在多了最后的T，所以多一步插入操作，dp[8][7] + 1

假设已经得到dna1前7个序列变成dna2前7个序列的最小操作距离dp[7][7]，现在dna1前7个序列后面多了碱基序列C，现在dna2前7个序列后面多了碱基序列T，因为C和T不同，那么需要在dp[7][7]的基础上再加一步替换操作，把C替换成T，当然这是本例的情况，如果它们一样都是T，那么不用操作，即：


AGCTTAG_ -> AGCTAGC_  假设得到最小操作距离为 dp[7][7]
AGCTTAGC -> AGCTAGCT  方法之一是先对前7个序列操作变成目标序列的前7个序列，
											现在两边分别多了最后的C和T，所以多一步插入操作，dp[7][7] + 1
											如果多的一样，都是T，那么不用操作，还是 dp[7][7]

这样类比上去，利用状态转移方程从dp[1][1]开始推算，得到最终的dp[8][8]

代码


public static int solution(String dna1, String dna2) {
        int m = dna1.length();
        int n = dna2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化第一行和第一列
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int cost = dna1.charAt(i - 1) == dna2.charAt(j - 1) ? 0 : 1;
                dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost));
            }
        }
        return dp[m][n];
    }

细节

DNA序列还原

解法：

相似题