我用记忆化搜索递归调用cmp函数，原先是这么写的
int cmp(int aend,int bend){
      if(record[aend][bend]>OMIN) { return (record[aend][bend]); }
      int i,j,k,temp;
      i=aend;
      j=bend;
      k=OMIN;
      if(aend>=2&&bend>=2)
      {
      
      temp=value[a[i]][b[j]]+cmp(i-1,j-1);
      k=MAX(k,temp);
      temp=value[a[i]][B]+cmp(i-2,j-1)+value[a[i-1]][b[j]];
      k=MAX(k,temp);
      temp=value[B][b[j]]+cmp(i-1,j-2)+value[a[i]][b[j-1]];
      k=MAX(k,temp);
      }

后来这么改了
if(aend>=2&&bend>=2)
      {
      
      temp=value[a[i]][b[j]]+cmp(i-1,j-1);
      k=MAX(k,temp);
      temp=value[a[i]][B]+cmp(i-1,j);
      k=MAX(k,temp);
      temp=value[B][b[j]]+cmp(i,j-1);
      k=MAX(k,temp);
      }

只是cmp(i-2,j-1)+value[a[i-1]][b[j]]不一样。按理这不应该是等价的吗？不理解，求解答。万分感谢

*********完整代码******************
#include<stdio.h>
#include<string.h>
#define N 101
#define OMIN -32000
#define MAX(a,b) (a)>(b)?(a):(b)
#define PAU //system("pause")
#include<stdlib.h>
#define A 1
#define B 5
#define C 2
#define G 3
#define T 4
// #define SUM

int record[N][N],ans[N];
char oria[N],orib[N];
int value[6][6],a[N],b[N];

int cmp(int aend,int bend){
      if(record[aend][bend]>OMIN) { return (record[aend][bend]); }
      int i,j,k,temp;
      i=aend;
      j=bend;
      k=OMIN;
      if(aend>=2&&bend>=2)
      {
      
      temp=value[a[i]][b[j]]+cmp(i-1,j-1);
      k=MAX(k,temp);
      temp=value[a[i]][B]+cmp(i-1,j);
      k=MAX(k,temp);
      temp=value[B][b[j]]+cmp(i,j-1);
      k=MAX(k,temp);
      }
      else{
           if(i==1&&j==1) k=value[a[1]][b[1]];
           else {
                k=OMIN;
                int sum=0,go;
                if(i==1) {
                    for(go=1;go<=j;go++) sum+=value[B][b[go]];
                    for(go=1;go<=j;go++)  {
                                          temp=sum-value[B][b[go]]+value[a[1]][b[go]];
                                          k=MAX(k,temp);
                                          }
      
                          }
                else{
                    for(go=1;go<=i;go++) sum+=value[B][a[go]];
                    for(go=1;go<=i;go++)  {
                                          temp=sum-value[B][a[go]]+value[b[1]][a[go]];
                                          k=MAX(k,temp);
                                          }
                     
                     }
          } 
          
          }
      
      record[aend][bend]=k;
      return k;
                                 }


#define DEBUGinput
int main(){
    int testcase,count=1;
    int lena,lenb,len,get,i,j;
    char temp;
    scanf("%d",&testcase);
    value[A][A]=5;value[A][C]=value[C][A]=-1;value[A][G]=value[G][A]=-2;
    value[A][T]=value[T][A]=-1;value[A][B]=value[B][A]=-3;
    
    value[C][C]=5;value[C][G]=value[G][C]=-3;value[C][T]=value[T][C]=-2;
    value[C][B]=value[B][C]=-4;
    
    value[G][G]=5;value[G][T]=value[T][G]=-2;value[G][B]=value[B][G]=-2;
    value[T][T]=5;value[T][B]=value[B][T]=-1;
    value[B][B]=OMIN;
    memset(ans,OMIN,sizeof(ans));
    while(testcase>=count){
                      memset(a,0,sizeof(a));
                      memset(b,0,sizeof(b));
                      memset(oria,0,sizeof(oria));
                      memset(orib,0,sizeof(orib));
                      scanf("%d%c",&lena,&temp);
                      #ifdef DEBUGwa
                      printf("%d\n",record[5][3]);
                      #endif
                      for(i=1;i<=lena;i++)  {
                                            scanf("%c",&oria[i]);
                                            switch(oria[i]){
                                            case 'A':a[i]=A;break;
                                            case 'G':a[i]=G;break;           
                                            case 'C':a[i]=C;break;             
                                            case 'T':a[i]=T;break;             
                                                         
                                                         }
                                            }
                      
                      scanf("%d%c",&lenb,&temp);
                      
                      for(i=1;i<=lenb;i++) {
                                           scanf("%c",&orib[i]);
                                           switch(orib[i]){
                                            case 'A':b[i]=A;break;
                                            case 'G':b[i]=G;break;           
                                            case 'C':b[i]=C;break;             
                                            case 'T':b[i]=T;break;             
                                                         
                                                         }
                                           }
                      
                      #ifdef DEBUGinputA
                      printf("testcase=%d count=%d\n",testcase,count);
                      for(i=1;i<=lena;i++) printf("%d ",a[i]);
                      printf("\n");
                      for(i=1;i<=lenb;i++) printf("%d ",b[i]);
                      printf("\n");
                      PAU;
                      #endif
                      len=MAX(lena,lenb);
                      for(i=0;i<=len+1;i++)
                      for(j=0;j<=len+1;j++) record[i][j]=OMIN;
                      
                      get=cmp(lena,lenb);
                      ans[count]=get;                     
                      count++;
                      #ifdef DEBUG
                      printf("count=%d get=%d\n",count,get);
                      #endif
                      }
    for(count=1;count<=testcase;count++) printf("%d\n",ans[count]);
    //printf("%d",ans[count]);
    PAU;
    return 0;
           }

• 我貌似明白了 (117) cotton 2011-01-25 15:18:14