洛谷线性动态规划训练（4）P1140 相似基因——串匹配，二维线性动态规划典例

输入格式
共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含A,C,G,TA,C,G,T四个字母。1 \le1≤序列的长度\le 100≤100。

输出格式
仅一行，即输入基因的相似度。

输入输出样例

输入 #1复制
7 AGTGATG
5 GTTAG
输出 #1复制
14

要点目录

1.如何根据最后一步得到状态转移方程
2.初始条件的确定与计算顺序
3.数据的输入
本题可参考zhy123456的题解，图像非常清晰
https://www.luogu.org/problemnew/solution/P1140

1 状态方程的获得

题目给出的数据是2个串的匹配，要求找到最大的匹配相似度的方案。如果使用一维dp[i]还是有点困难的，因为它给了2行数据，互相之间是影响的。因此考虑使用二维dp[i][j]，问题是这个状态如何确定呢？ 考虑最后一步，也就是说不管两个不等长的串如何匹配，他们最后匹配完的时候总是由前面匹配完，再加上最后一个字符的匹配，这样才构成了整个的匹配方案。那么最后一个字符之间的相互匹配，可能就是互相之间都出一个字符，或者串1出字符，串2空；或者串1空，串2出字符。也就是总共只有3种可能。

因此我们将dp[i][j]定义为：串1的1-i序列与串2的1-j序列匹配得到的最大的相似度。

2 初始条件的确定与计算顺序

由图可知，计算顺序是从上到下，从左往右。关键是dp[i][0]和dp[0][i]如何计算。注意到，dp[i][0]实际上就是串1的1-i序列和空序列互相匹配。转化为dp[i-1][0]+Gen1[i][5]，即第i个基因和空基因匹配。类似的可以计算dp[0][i]

3 数据的输入

首先是输入的数字ch，然后根据对应的字符可以转化为数字1-4.转化为1-4的原因是为了方便后面的匹配，匹配使用的是矩阵，因此转换为数字非常合适。

代码

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

int v[6][6] = {
	{ 0,0,0,0,0,0 },
	{ 0,5,-1,-2,-1,-3 },
	{ 0,-1,5,-3,-2,-4 },
	{ 0,-2,-3,5,-2,-2 },
	{ 0,-1,-2,-2,5,-1 },
	{ 0,-3,-4,-2,-1,0 }
};

int main() {
	int Gen1[105];
	int Gen2[105];
	int dp[105][105] = {};
	int len1, len2;
	//读取数据进行转化
	char ch;
	cin >> len1;
	for (int i = 1; i <= len1; i++) {
		cin >> ch;
		if (ch == 'A')Gen1[i] = 1;
		if (ch == 'C')Gen1[i] = 2;
		if (ch == 'G')Gen1[i] = 3;
		if (ch == 'T')Gen1[i] = 4;
	}
	cin >> len2;
	for (int i = 1; i <= len2; i++) {
		cin >> ch;
		if (ch == 'A')Gen2[i] = 1;
		if (ch == 'C')Gen2[i] = 2;
		if (ch == 'G')Gen2[i] = 3;
		if (ch == 'T')Gen2[i] = 4;
	}
	//数据处理，计算初始值
	dp[0][0] = 0;
	for (int i = 1; i <=len1; i++) {
		dp[i][0] = dp[i - 1][0] + v[Gen1[i]][5];
	}
	for (int i = 1; i <= len2; i++) {
		dp[0][i] = dp[0][i - 1] + v[5][Gen2[i]];
	}
	//状态转移方程
	for (int i = 1; i <= len1; i++) {
		for (int j = 1; j <= len2; j++) {
			dp[i][j] = max({ dp[i - 1][j - 1] + v[Gen1[i]][Gen2[j]],dp[i - 1][j] + v[Gen1[i]][5],dp[i][j - 1] + v[5][Gen2[j]] });
		}
	}
	cout << dp[len1][len2];
	return 0;
}