題目地址

這是一道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;
}