题意分析

此代码用于解决 DNA 序列比对问题，要让两个 DNA 序列比对得分最小。

解题思路

得分矩阵定义：借助$scoreMatrix$明确不同字符匹配时的得分。 字符转换：通过$charToIndex$函数把字符$'A'、'G'、'C'、'T'$转换成得分矩阵的索引。 动态规划求解： 运用二维数组dp来记录子问题的解。 对边界条件进行初始化，也就是一个序列为空时的得分。 采用动态规划填充表格，针对每个位置$(i, j)$，考虑三种情况：匹配两个字符、在$seq2$中插入空位、在$seq1$中插入空位，选取最小得分。

C++实现

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 得分矩阵
const int scoreMatrix[4][4] = {
	{0, 3, 4, 3},
	{3, 0, 3, 4},
	{4, 3, 0, 3},
	{3, 4, 3, 0}
};

// 将字符转换为矩阵索引
int charToIndex(char c) {
	switch (c) {
		case 'A': return 0;
		case 'G': return 1;
		case 'C': return 2;
		case 'T': return 3;
		default: return -1;
	}
}

// 计算两个序列比对的最小得分
int minAlignmentScore(const string& seq1, const string& seq2) {
	int m = seq1.length();
	int n = seq2.length();
	// 提前处理空序列的情况
	if (m == 0) return 4 * n;
	if (n == 0) return 4 * m;
	
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	
	// 初始化边界条件
	for (int i = 1; i <= m; ++i) {
		dp[i][0] = dp[i - 1][0] + 4;
	}
	for (int j = 1; j <= n; ++j) {
		dp[0][j] = dp[0][j - 1] + 4;
	}
	
	// 动态规划填充表格
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			int matchScore = scoreMatrix[charToIndex(seq1[i - 1])][charToIndex(seq2[j - 1])];
			if (matchScore == -1) {
				// 处理非法字符的情况
				return -1; 
			}
			dp[i][j] = min({
				dp[i - 1][j - 1] + matchScore,  // 匹配两个字符
				dp[i - 1][j] + 4,  // 在 seq2 中插入空位
				dp[i][j - 1] + 4   // 在 seq1 中插入空位
			});
		}
	}
	
	return dp[m][n];
}

int main() {
	string seq1, seq2;
	while (cin >> seq1 >> seq2) {
		int score = minAlignmentScore(seq1, seq2);
		if (score == -1) {
			cout << "Invalid input" << endl;
		} else {
			cout << score << endl;
		}
	}
	return 0;
}