青训1_1105_02 DNA序列编辑距离(动态规划_不好理解)

青训1_1105_02 DNA序列编辑距离(动态规划_不好理解)

问题描述

问题描述
小R正在研究DNA序列，他需要一个函数来计算将一个受损DNA序列（dna1）转换成一个未受损序列（dna2）所需的最少编辑步骤。编辑步骤包括：增加一个碱基、删除一个碱基或替换一个碱基。

测试样例

样例1：

输入：dna1 = "AGT",dna2 = "AGCT"
输出：1

样例2：

输入：dna1 = "AACCGGTT",dna2 = "AACCTTGG"
输出：4

样例3：

输入：dna1 = "ACGT",dna2 = "TGC"
输出：3

样例4：

输入：dna1 = "A",dna2 = "T"
输出：1

样例5：

输入：dna1 = "GGGG",dna2 = "TTTT"
输出：4

示例

def solution(dna1, dna2):
    # Please write your code here
    return -2

if __name__ == "__main__":
    #  You can add more test cases here
    print(solution("AGCTTAGC", "AGCTAGCT") == 2 )
    print(solution("AGCCGAGC", "GCTAGCT") == 4)

思路(ERROR)

左->右，只有增加、删除、替换

思路（right）_我也不是很理解

1、创建(m+1)×(n+1)的dp数组,其中m和n分别是两个字符串的长度
2、初始化:
dp[i][0] = i (删除i个字符)
dp[0][j] = j (插入j个字符)

3、对于每个位置(i,j),考虑:
3.1 如果dna1[i-1] == dna2[j-1],则dp[i][j] = dp[i-1][j-1]
3.2 否则取三种操作的最小值:

替换: dp[i-1][j-1] + 1
插入: dp[i][j-1] + 1
删除: dp[i-1][j] + 1

答案

def solution(dna1, dna2):
    m, n = len(dna1), len(dna2)
    
    # 创建dp数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化第一行和第一列
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
        
    # 填充dp数组
    for i in range(1, m + 1):
        for j in range(1, n + 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] + 1,  # 替换
                    dp[i-1][j] + 1,    # 删除
                    dp[i][j-1] + 1     # 插入
                )
    
    return dp[m][n]

if __name__ == "__main__":
    #  You can add more test cases here
    print(solution("AGCTTAGC", "AGCTAGCT") == 2 )
    print(solution("AGCCGAGC", "GCTAGCT") == 4)

原文地址：https://blog.csdn.net/qq_40266376/article/details/143533811

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！