问题描述：
-
众所周知，人类基因可以认为是一个基因序列，包含四种核苷酸，分别用A，C，T和G四个字母简单地表示。生物学家对鉴别人类基因并确定他们的功能很感兴趣，因为这对诊断人类疾病和开发新药很有用。……
-
你的任务是编写一个程序，按以下规则比较两个基因并确定它们的相似程度。
-
给出两个基因AGTGATG和GTTAG，他们有多相似呢？测量两个基因相似度的一种方法称为对齐。使用对齐方法，可以在基因的适当位置插进空格，让两个基因的长度相等，然后根据基因分值矩阵（下图表格）计算分数。
-
例如，给AGTGATG插入一个空格，就得到AGTGAT-G；给GTTAG插入三个空格，就得到-GT–TAG。空格用减号（-）表示。现在两个基因一样长了，把这两个字符串对齐：
AGTGAT-G
-GT–TAG -
对齐以后，有四个基因是相配的：第二位的G，第三位的T，第六位的T和第八位的G。根据下列基因分值矩阵，每对匹配的字符都有相应的分值。
-
“*”表示空格对空格是不允许的。上面对齐的字符串分值是：
(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。 -
当然，还有其它的对齐方式。下面是另一种对齐方式(不同数量的空格插进不同的位置)：
AGTGATG
-GTTA-G -
这种对齐方式的分值是(-3)+5+5+(-2)+5+(-1) +5=14，它比前一个要好。其实这种对齐方式是最优的，没有其他的方式能得到更高的分值了，所以这两个基因的相似度是14。
输入样例
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
输出样例
14
21
算法分析：
1、数据结构
基因分值矩阵的表示：
int score[5][5] =
{ {5, -1, -2, -1, -3},
{-1, 5, -3, -2, -4},
{-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1},
{-3, -4, -2, -1, 0}}; -
原矩阵的下标是’A’，‘C’，‘G’，‘T’和’-’，有很多程序采用switch语句转换，这里采用map数组转换： char
map[128]; -
只使用其中5个单元：map[‘A’] = 0; map[‘C’] = 1; map[‘G’] = 2; map[‘T’] = 3;map[’-’] = 4;
-
两个基因使用字符串表示： char str1[MaxN],str2[MaxN];
2、动态规划算法的实现
-
本题类似于最长公共子序列（LCS）问题。
-
使用gene数组记录动态规划过程中产生的中间结果： int gene[MaxN][MaxN];
-
gene[i][j]表示基因子串str1[0…i-1]和str2[0…j-1]的分值：
-
str1取第i-1个字母，str2取’-’：
m1 = gene[i-1][j] + score[map[str1[i-1]]][4]; -
str1取’-’，str2取第j-1个字母：
m2 = gene[i][j-1] + score[4][map[str2[j-1]]]; -
str1取第i-1个字母，str2取第j-1个字母：
m3 = gene[i-1][j-1] +score[map[str1[i-1]]][map[str2[j-1]]];
则gene[i][j] = **max**(m1, m2, m3)。
最终结果是gene[first][second]。
下标问题：字符串str1, str2的下标是从0开始的，数组gene中的下标是从1开始的，所以下标差一个值。
- 边界条件就是i或j为0的情况，分3种情况：
(1) 当i=0, j=0时，没有任何基因字母就没有分值，gene[0][0] = 0；
(2) 当i=0时，即为gene [0,1…second] ：
for(i = 1 ; i <= second;i++) gene[0][i] = gene[0][i-1]+score[4][map[str2[i-1]]];
(3) 当j=0时，即为gene [1…first, 0] ：
for(i = 1 ; i <= first;i++) gene[i][0] = gene[i-1][0]+score[map[str1[i-1]]][4];
3、计算两个基因相似度的算法
scanf("%d%s", &first, str1); //第1个基因信息
scanf("%d%s", &second, str2); //第2个基因信息
//计算动态规划算法的边界条件
gene[0][0] = 0;
for(i = 1 ; i <= second;i++) gene[0][i] = gene[0][i-1]+score[4][map[str2[i-1]]];
for(i = 1 ; i <= first;i++) gene[i][0] = gene[i-1][0]+score[map[str1[i-1]]][4];
//求解最优值
int m1,m2,m3;
for(i = 1; i<=first;i++)for(j = 1; j<=second; j++){
m1 = gene[i-1][j]+score[map[str1[i-1]]][4];m2 = gene[i][j-1]+score[4][map[str2[j-1]]];m3 = gene[i-1][j-1]+score[map[str1[i-1]]][map[str2[j-1]]];gene[i][j] = max(m1,max(m2,m3));}