這是一道DP的題目 搜索肯定解決不了 只能DP
DP的麻煩在于 如何確定狀態(tài)
如何列出狀態(tài)轉移方程
score[i][j]代表每個對應分數(shù)
input1 input2表示2列基因字母n和m是長度
dp[i][j]表示input2的第i個字母 對應input1 j-1字母所得的分數(shù)
j為0的時候代表 對應空字母
對于input2的第一個點 對面有n+1種情況
即對應對應空 或者對應input的0到n-1位置
j=0時
dp[0][0]=score[input2[0]][4];
j>0時
dp[0][j]=sum(score[4][0.....j-2])+score[input2[0]][input1[j-1]]
狀態(tài)轉移方程
有2種情況
如果input2的第i-1點對應的是input1 j-1點 那么第i個點只能對應空
value=dp[i-1][j]+score[input2[i]][4];
如果input2的第i-1點對應的是input1 0到j-2直接的數(shù)或者對應空
那么第i個點對應input1的j-1點
value=dp[i-1][k]+sum(score[4][k.....j-2])+score[input2[i]][input1[j-1]]
k from 0 to j-1
最后取最大值得到dp[i][j]
最后處理下input1未對應的點
然后取最后一行的最大值 就是結果
#include <stdio.h>
int getIndex(char c){
switch (c)
{
case 'C':
return 1;
case 'G':
return 2;
case 'T':
return 3;
case 'A':
return 0;
default:
return -1;
}
}
const int MaxLen=200;
int* getInputArray(int n,char input[MaxLen])
{
char c;
int i=0,j=0;
int* input1=new int[n];
do
{
c=input[i];
int index=getIndex(c);
if(index>=0)
{
input1[j]=index;
j++;
}
i++;
}while (c!='\0'&&j<n);
return input1;
}
void printArray(int** dp,int m,int n)
{
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
printf("%d\t",dp[i][j]);
}
printf("\n");
}
}
int main(){
int n,m;
//每個對應關系的得分
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}};
int i,j,k;
char input[MaxLen];
scanf("%d %s",&n,input);
int* input1=getInputArray(n,input);
scanf("%d %s",&m,input);
int* input2=getInputArray(m,input);
int n1=n+1;
int m1=m+1;
int** dp=new int*[m1];
for(i=0;i<m1;i++)
{
dp[i]=new int[n1];
}
int* sumScore=new int[n1];
sumScore[0]=0;
//sumScore[i] input1 0到i-1元素對應空的時候的和
for(i=1;i<n1;i++)
{
sumScore[i]=sumScore[i-1]+score[4][input1[i-1]];
}
//計算第0行的值
dp[0][0]=score[input2[0]][4];
for(i=1;i<n1;i++)
{
dp[0][i]=sumScore[i-1]+score[input2[0]][input1[i-1]];
}
for(i=1;i<m;i++)
{
for(j=0;j<n1;j++)
{
//i-1對應j-1的情況
int max=dp[i-1][j]+score[input2[i]][4];
for(k=0;k<j;k++)
{
//i-1對應k的情況
int value=dp[i-1][k]+sumScore[j-1]-sumScore[k]+score[input2[i]][input1[j-1]];
if(value>max)
{
max=value;
}
}
dp[i][j]=max;
}
}
int max=-(m+n)*5;
//處理input1 剩下未對應的點 計算出最終結果
for(i=0;i<n1;i++)
{
dp[m][i]=dp[m-1][i]+sumScore[n]-sumScore[i];
if(max<dp[m][i])
{
max=dp[m][i];
}
}
// printArray(dp,m1,n1);
delete input1;
delete input2;
delete sumScore;
for(i=0;i<m1;i++)
{
delete dp[i];
}
delete dp;
printf("%d\n",max);
return 0;
}