DNA序列编辑距离 : [题目链接](DNA序列编辑距离 - MarsCode)

这是一道相当经典的 dp 题 , 在力扣中也有类型的原题 , 链接如下72. 编辑距离

如果对dp题识别敏感度不高的可以看看我下面的理解

dp 题的思考思路 :

我们要对两个方面都敏感 , 1. 小推大的 递推关系 2. 大推小的 寻找子问题

对于 dp 要大胆猜想 , 可能不一定是线性的递推, 也可能是跳跃式的递推

还有一个很重要的点 , 在想递推的时候 , 我们要想的方向是连续性的递推感 , 递推的前一个元素不要想太细 , 想成抽象化的模型 , 意思就是别把一个元素的推导由来不要想成最初态推导而来 , 而是进行了一段连续性递推后得来的 , 这种感觉在二叉树的递推也有类似的身影 , 我们在想根节点的向下扩展时 , 想的是分为左子树和右子树这两个抽象的模型 , 而不是左节点和右节点这种细化的初始态 , 并且能保证左子树和右子树能当成根节点 ,这种思考方式就符合连续性的递推感

回到题目中 :这道题的关键在于编辑步骤包括：增加一个碱基、删除一个碱基或替换一个碱基。

我就是从这里判断出为动态规划的 , 增加一个碱基 ,删除一个碱基 , 替换一个碱基都是跟子问题有一定关系

定义dp 数组 :

dp[i][j] 表示以下标i-1为结尾的字符串dna1，和以下标j-1为结尾的字符串dna2，最近编辑距离为dp[i][j] 。

dp的递推推导删除操作 dp[i][j] = dp[i - 1][j] + 1 表示直接跳过i-1的配对 , 并让其操作数 + 1替换操作 dp[i][j] = dp[i - 1][j - 1] + 1 表示直接跳过i-1和j-1的配对, 因为替换就是让两个匹对成功插入操作 dp[i][j] = dp[i][j - 1] + 1 表示让新插入的与j-1配对 , 则原本的i不变 , j = j - 1 配对成功不操作 dp[i][j] = dp[i - 1][j - 1]; 默认配对成功 ,操作数不变

注意: 这里的操作都是对dna1 ,元素i的操作

完整代码如下

#include 
#include 
int solution(std::string dna1, std::string dna2) {
    int n = dna1.size() , m = dna2.size();
    std::vectorint>> dp(n+1 , std::vector<int>(m+1 , INT_MAX));
    for(int i = 0; i <= n; i++) dp[i][0] = i;
    for(int j = 0; j <= m; j++) dp[0][j] = j;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(dna1[i-1] == dna2[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = std::min({dp[i-1][j]+1 , dp[i][j-1]+1 , dp[i-1][j-1]+1});
    return dp[n][m];
}
int main() {
    //  You can add more test cases here
    std::cout << (solution("AGCTTAGC", "AGCTAGCT") == 2) << std::endl;
    std::cout << (solution("AGCCGAGC", "GCTAGCT") == 4) << std::endl;
    return 0;
}

def solution(dna1, dna2):
    len1 = len(dna1)
    len2 = len(dna2)
    # 创建一个二维数组 dp
    dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
    # 初始化边界条件
    for i in range(len1 + 1):
        dp[i][0] = i  # 删除所有字符
    for j in range(len2 + 1):
        dp[0][j] = j  # 插入所有字符
    # 填充 dp 表
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if dna1[i - 1] == dna2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # 字符相同，不需要操作
            else:
                dp[i][j] = min(
                    dp[i - 1][j] + 1,    # 删除
                    dp[i][j - 1] + 1,    # 插入
                    dp[i - 1][j - 1] + 1  # 替换
                )
    return dp[len1][len2]
if __name__ == "__main__":
    print(solution("AGCTTAGC", "AGCTAGCT") == 2)
    print(solution("AGCCGAGC", "GCTAGCT") == 4)
    print(solution("AGT", "AGCT") == 1)
    print(solution("AACCGGTT", "AACCTTGG") == 4)
    print(solution("ACGT", "TGC") == 3)
    print(solution("A", "T") == 1)
    print(solution("GGGG", "TTTT") == 4)