程序填空题：求解人类基因功能问题（动态规划）

求解人类基因功能问题。人类基因被认为由4个核苷酸组成的序列，简单地由4个字母A、C、G和T表示。科学家认为，基因序列的相似性往往意味着功能的相似性，因此需要找出相似的基因序列，以此确定新基因序列的功能。请编写一个比较两个基因并确定它们相似性的程序。
给定两个基因AGTGATG和GTTAG，它们有多相似？测量两个基因相似性的一种方法称为对齐。在对齐中，如果需要，在基因的适当位置插入空格以使它们等长，并根据评分矩阵评分所得基因。
例如：在AGTGATG中插入一个空格得到：AGTGAT_G，并且在GTTAG中插入3个空格得到_GT__TAG。现在两个基因等长，根据评分矩阵计算得分为(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。如果采用如下对齐方式：AGTGATG和_GTTA_G，则对齐得分是(-3)+5+5+(-2)+5+(-1)+5=14。事实上这是一个最佳的对齐方式，因为没有其他对齐可以有更高的得分，14这就是两个基因的相似性。




```c++
#include
#include
#include
#include
using namespace std;
#define MAX 110

char s[MAX],t[MAX];
int dp[MAX][MAX];
int matrix[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}};
int n,m;
char Ch[5]={'A','C','G','T',' '};
int value(char ch1,char ch2);
int simliarity();
int value(char ch1,char ch2)
{
int r,c;
for(int i=0;i<5;i++){
if(Ch[i]==ch1)
r=i;
if(Ch[i]==ch2)
c=i;
}
return matrix[r][c];
}
int main()
{ cin>>s>>t;
memset(dp,0,sizeof(dp));
cout< return 0;
}

int simliarity()
{
int i,j;
dp[0][0]=0;
n=strlen(s);
m=strlen(t);
for (i=1;i<=n;i++)
dp[i][0]=;
for (j=1; j<=m; j++)
dp[0][j]=;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
dp[i][j]=max(dp[i-1][j]+value(s[i-1],' '),max(dp[i][j-1]+value(' ',t[j-1]),dp[i-1][j-1]+value(s[i-1],t[j-1])));
}
return ;
}
```
### 输入格式:

分别输入两个基因序列，各占一行。

### 输出格式:

输出相似性。

### 输入样例1:

```in
AGTGATG
GTTAG
```

### 输出样例1:

```out
14
```





答案：
第1空：dp[i-1][0]+value(s[i-1],' ')

第2空：dp[0][j-1]+value(' ',t[j-1])

第3空：dp[n][m]