动态规划(DP)，Human Gene Functions-白红宇

动态规划(DP)，Human Gene Functions

阅读量：6519 次

发布时间：2019-06-24

本文共 1620 字，大约阅读时间需要 5 分钟。

题目链接：

解题报告：

1、类似于LCS

2、gene[i][j]表示str1[i-1]和str2[j-1]的分值串没有，则应该扣分

3、递推公式

temp1=gene[i-1][j-1]+score[_map[str1[i-1]]][_map[str2[j-1]]];

temp2=gene[i-1][j]+score[_map[str1[i-1]]][4];

temp3=gene[i][j-1]+score[4][_map[str2[j-1]]];

gene[i][j]=max(temp1,max(temp2,temp3));

4、在初始化边界条件时，认为一个字符串为空，则要扣分

#include 
     
      #include 
      
       #include 
       #define NUM 105using namespace std;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}};map
        
          _map;char str1[NUM],str2[NUM];int len1,len2;int gene[NUM][NUM];///gene[i][j]表示基因子串str1[i-1]和str2[j-1]的分值.int main(){    _map['A']=0,_map['C']=1,_map['G']=2,_map['T']=3,_map['-']=4;    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d%s",&len1,str1);        scanf("%d%s",&len2,str2);        ///初始化边界条件        gene[0][0]=0;        for(int i=1; i<=len1; i++)            gene[i][0]=gene[i-1][0]+score[_map[str1[i-1]]][4];        for(int i=1; i<=len2; i++)            gene[0][i]=gene[0][i-1]+score[4][_map[str2[i-1]]];        int m1,m2,m3;        for(int i=1; i<=len1; i++)        {            for(int j=1; j<=len2; j++)            {                m1=gene[i-1][j]+score[_map[str1[i-1]]][4];///str1取i-1个字符，str2取'-';                m2=gene[i][j-1]+score[4][_map[str2[j-1]]];///str1取'-',str2取j-1个字符;                m3=gene[i-1][j-1]+score[_map[str1[i-1]]][_map[str2[j-1]]];///str1取i-1个字符，str2取j-1个字符                gene[i][j]=max(m1,max(m2,m3));            }        }        printf("%d\n",gene[len1][len2]);    }    return 0;}