题目地址

这是一道DP的题目 搜索肯定解决不了 只能DP
DP的麻烦在于 如何确定状态
如何列出状态转移方程

score[i][j]代表每个对应分数
input1 input2表示2列基因字母n和m是长度
dp[i][j]表示input2的第i个字母 对应input1 j-1字母所得的分数
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]]

状态转移方程
有2种情况
如果input2的第i-1点对应的是input1 j-1点 那么第i个点只能对应空
value=dp[i-1][j]+score[input2[i]][4];
如果input2的第i-1点对应的是input1 0到j-2直接的数或者对应空
那么第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;
}