引用：

用二维数组f储存第1个基因前i个与第2个基因前j个的最大匹配值

先将字符串转化为数组储存

将f初始化为一个很小的值

因为第1个基因前i个与第2个基因第0个匹配肯定是与空碱基匹配的值

首先建立一个table，存入各个基因相似度（如下）

const int tab[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}

};

接着进行一波预处理：

for(int i=1;i<=la;i++) for(int j=1;j<=lb;j++) dp[i][j]=-2e8;//设置极小值

for(int i=1;i<=la;i++)

{

if(sa[i-1]==’A’) a[i]=0;

if(sa[i-1]==’C’) a[i]=1;

if(sa[i-1]==’G’) a[i]=2;

if(sa[i-1]==’T’) a[i]=3;

}//将字符转换为表中对应的编号

for(int i=1;i<=lb;i++)

{

if(sb[i-1]==’A’) b[i]=0;

if(sb[i-1]==’C’) b[i]=1;

if(sb[i-1]==’G’) b[i]=2;

if(sb[i-1]==’T’) b[i]=3;

}//同上

然后开始动态规划：

1.（特判）因为第一/二段的1与第二/一段的0匹配时可视作与空碱基匹配，所以先进行一波预处理：

for(int i=1;i<=la;i++) dp[i][0]=dp[i-1][0]+tab[a[i]][4];

for(int i=1;i<=lb;i++) dp[0][i]=dp[0][i-1]+tab[b[i]][4];

2.接着逐个判断即可得出三条状态转移方程，取三种配对方法（1.一中插空碱基；2.二中插空碱基；3.直接配对）所得结果中最优的一种。

（上伪代码）

{ 若在第一段基因中插入空碱基相似度更优 则在第一段插入空碱基

若在第二段基因中插入空碱基相似度更优 则在第二段插入空碱基

若直接配对的相似度高于以上两者 则直接插入

for(int i=1;i<=la;i++)
for(int j=1;j<=lb;j++)
{
dp[i][j]=max(dp[i][j],dp[i][j-1]+tab[b[j]][4]);
dp[i][j]=max(dp[i][j],dp[i-1][j]+tab[a[i]][4]);
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+tab[a[i]][b[j]]);
}
} 3.最后输出结果即可。

//my ac code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int max(int a,int b){return a>b?a:b;}
int jianji[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 dp[105][105],l1,l2,sa[105],sb[105];
string s1,s2;
int main(){
   cin >> l1 >> s1 >> l2 >> s2;
   for(int i=1;i<=l1;i++)for(int j=1;j<=l2;j++)dp[i][j]=-520520520;
   for(int i=1;i<=l1;i++){
       if(s1[i-1]=='A')sa[i]=0;
       if(s1[i-1]=='C')sa[i]=1;
       if(s1[i-1]=='G')sa[i]=2;
       if(s1[i-1]=='T')sa[i]=3;
   }
   for(int i=1;i<=l2;i++){
       if(s2[i-1]=='A')sb[i]=0;
       if(s2[i-1]=='C')sb[i]=1;
       if(s2[i-1]=='G')sb[i]=2;
       if(s2[i-1]=='T')sb[i]=3;
   }
   for(int i=1;i<=l1;i++)dp[i][0]=dp[i-1][0]+jianji[sa[i]][4];
   for(int i=1;i<=l2;i++)dp[0][i]=dp[0][i-1]+jianji[sb[i]][4];
   for(int i=1;i<=l1;i++){
       for(int j=1;j<=l2;j++){
           dp[i][j]=max(dp[i][j],dp[i-1][j]+jianji[sa[i]][4]);
           dp[i][j]=max(dp[i][j],dp[i][j-1]+jianji[sb[j]][4]);
           dp[i][j]=max(dp[i][j],dp[i-1][j-1]+jianji[sa[i]][sb[j]]);
       }
   }
   printf("%d",dp[l1][l2]);
    return 0;
}