1.编写一个基于动态规划算法的DNA序列比对函数，给出两条序列（V和W）的打分矩阵，自由定义罚分规则；

动态规划是一种解决复杂优化问题的有效方法，特别适用于求解最优化问题，如DNA序列比对。在这个场景下，我们可以创建一个二维数组（称为得分矩阵），其中每个元素表示两个DNA序列中对应位置字符匹配、插入或删除的成本。通常，A对A得高分（比如1），其他配对如G-C或T-A得较低分数（例如0或负数），而插入或删除通常会有一定的惩罚分数（如负数）。下面是一个基本的动态规划函数设计：

def dp_dna_alignment(V, W, match_score=1, mismatch_score=-1, gap_penalty=-2):
    m, n = len(V), len(W)
    dp_matrix = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化边界条件
    for i in range(m + 1):
        dp_matrix[i][0] = i * gap_penalty   # 对于V来说，向右插入的代价随着长度增加
    for j in range(n + 1):
        dp_matrix[0][j] = j * gap_penalty   # 对于W来说，向下插入的代价同样增加

    # 动态填充得分矩阵
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if V[i - 1] == W[j - 1]:
                dp_matrix[i][j] = dp_matrix[i - 1][j - 1] + match_score
            else:
                dp_matrix[i][j] = max(dp_matrix[i - 1][j] + gap_penalty,  # 删除
                                    dp_matrix[i][j - 1] + gap_penalty,  # 插入
                                    dp_matrix[i - 1][j - 1] + mismatch_score)  # 配对错误

    return dp_matrix, get_optimal_alignment(dp_matrix, V, W)

# 辅助函数用于获取最优路径
def get_optimal_alignment(dp_matrix, V, W):
    alignments = []
    i, j = len(V), len(W)
    
    while i > 0 and j > 0:
        if dp_matrix[i][j] == dp_matrix[i - 1][j] + gap_penalty:
            i -= 1  # 如果上一行有更高的得分，说明发生了删除操作
        elif dp_matrix[i][j] == dp_matrix[i][j - 1] + gap_penalty:
            j -= 1  # 否则，如果这一列有更高的得分，说明发生了插入操作
        else:
            alignments.append('D' if dp_matrix[i][j] == dp_matrix[i - 1][j - 1] + mismatch_score else 'M')
            i -= 1
            j -= 1
    
    return ''.join(alignments[::-1]), dp_matrix[-1][-1]

# 示例用法
V = "ATCG"
W = "ACTG"
score_matrix, optimal_alignment = dp_dna_alignment(V, W)
print("Score:", score_matrix[-1][-1])
print("Optimal Alignment:", optimal_alignment)

这个函数返回了两个值：一个是计算得到的总得分，另一个是两个序列的最佳比对结果。