[线性动态规划][P1140 相似基因][类LCS]做题记录和思考总结

题目地址

题目背景

大家都知道，基因可以看作一个碱基对序列。它包含了44种核苷酸，简记作A,C,G,TA,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。

在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。

 

题目思路：

该题类似于LCS（最长公共子序列）

首先想到两段基因配对共有三种情况：

1. 对应碱基对直接配对；
2. DNA序列1中某个碱基对和空白碱基对配对；
3. DNA序列2中某个碱基对和空白碱基对配对。

• 列出一个储存动态规划的二维数组：DP[i][j](i表示DNA序列1匹配到第i个时的最大值，j表示DNA序列2匹配到第j个时的最大值)
• 输出答案应输出DP[N][R].(N表示DNA序列1长度，R表示DNA序列2长度)

 

• 编写程序时做好相关预处理（详细请见代码）；

 

• 列出动态规划状态转移方程（状态转移方程含义配合代码理解）：

    

    

    

• 注意避开大坑：将所有DP元素设置为-127[或者其它合适的负值]（设置为0将不会得到正确答案） 

完整AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int DP[101][101] = {0};

int Cal[5][5] = {{0,-3,-4,-2,-1},
                {-3,5,-1,-2,-1},
				{-4,-1,5,-3,-2},
				{-2,-2,-3,5,-2},
				{-1,-1,-2,-2,5}};
				
int Pro(char);

int main(void)
{
	int N,R;
	char DNA1[102];
	char DNA2[102];
	cin >> N >> DNA1;
	cin >> R >> DNA2;
	
	int DNALine1[102] = {0};
	int DNALine2[102] = {0};
	
	for(int i = 1;i <= N;i++)
	{
		DNALine1[i] = Pro(DNA1[i-1]);
	}
	for(int i = 1;i <= R;i++)
	{
		DNALine2[i] = Pro(DNA2[i-1]);
	}
	
	
	memset(DP,-127,sizeof(DP)); 
	DP[0][0] = 0;
	
	/*预处理边界值*/
	for(int i = 1;i <= N;i++)
	{
		DP[i][0] = DP[i-1][0] + Cal[DNALine1[i]][0];
	}
	for(int j = 1;j <= R;j++)
	{
		DP[0][j] = DP[0][j-1] + Cal[0][DNALine2[j]];
	}
	
	for(int i = 1;i <= N;i++)
	{
		for(int j = 1;j <= R;j++)
		{
			//此处不添加空白基因 
			DP[i][j] = max(DP[i-1][j-1] + Cal[DNALine1[i]][DNALine2[j]],DP[i][j]);
			//在DNA序列1添加一个空白基因 
			DP[i][j] = max(DP[i-1][j] + Cal[DNALine1[i]][0],DP[i][j]);
			//在DNA序列2添加一个空白基因 
			DP[i][j] = max(DP[i][j-1] + Cal[0][DNALine2[j]],DP[i][j]);
		}
	}
	cout << DP[N][R] << endl;
	return 0;
}

int Pro(char ch)
{
	switch(ch)
	{
		case 'A':
		{
			return 1;
		}
		case 'C':
		{
			return 2;
		}
		case 'G':
		{
			return 3;
		}
		case 'T':
		{
			return 4;
		}
	}
	return 0;
}