poj-1080

#include <stdio.h>  #include <string.h>  int alignmentMatix[100][100] = {0};  int DPResult[101][101];  void init() {      alignmentMatix['A']['A'] = 5;      alignmentMatix['A']['C'] = -1;      alignmentMatix['A']['G'] = -2;      alignmentMatix['A']['T'] = -1;      alignmentMatix['A""""""" = -3;            alignmentMatix['C']['A'] = -1;      alignmentMatix['C']['C'] = 5;      alignmentMatix['C']['G'] = -3;      alignmentMatix['C']['T'] = -2;      alignmentMatix['C""""""" = -4;            alignmentMatix['G']['A'] = -2;      alignmentMatix['G']['C'] = -3;      alignmentMatix['G']['G'] = 5;      alignmentMatix['G']['T'] = -2;      alignmentMatix['G""""""" = -2;      alignmentMatix['T']['A'] = -1;      alignmentMatix['T']['C'] = -2;      alignmentMatix['T']['G'] = -2;      alignmentMatix['T']['T'] = 5;      alignmentMatix['T""""""" = -1;      alignmentMatix['''''''''''A'] = -3;      alignmentMatix['''''''''''C'] = -4;      alignmentMatix['''''''''''G'] = -2;      alignmentMatix['''''''''''T'] = -1;      alignmentMatix['-""""""" = -99999;  }  int getMaxSimilarity(char * Agene, char * Bgene, int Abegin, int Bbegin) {      // printf("%d %d\n", Abegin, Bbegin);      if (DPResult[Abegin][Bbegin] != 9999) {          return DPResult[Abegin][Bbegin];      } else {          int res;              if (Agene[Abegin] == 0 && Bgene[Bbegin] == 0) {              res = 0;          } else if (Agene[Abegin] == 0) {              int smiliarity = 0;              for (int i = 0; Bgene[Bbegin+i] != 0; i++) {                  smiliarity += alignmentMatix['-'][Bgene[Bbegin+i]];              }              res = smiliarity;          } else if (Bgene[Bbegin] == 0) {              int smiliarity = 0;              for (int i = 0; Agene[Abegin+i] != 0; i++) {                  smiliarity += alignmentMatix[Agene[Abegin+i]]['-'];              }              res = smiliarity;          } else {              int onlyA = alignmentMatix[Agene[Abegin]]['-'] + getMaxSimilarity(Agene, Bgene, Abegin+1, Bbegin);              int onlyB = alignmentMatix['-'][Bgene[Bbegin]] + getMaxSimilarity(Agene, Bgene, Abegin, Bbegin+1);              int both = alignmentMatix[Agene[Abegin]][Bgene[Bbegin]] + getMaxSimilarity(Agene, Bgene, Abegin+1, Bbegin+1);;              int AorBMax;              AorBMax = onlyA > onlyB ? onlyA : onlyB;              AorBMax = AorBMax > both ? AorBMax : both;              res = AorBMax;          }          DPResult[Abegin][Bbegin] = res;          return DPResult[Abegin][Bbegin];      }  }  int main() {      int caseNum = 0;      scanf("%d", &caseNum);      init();      for (int i = 0; i < caseNum; i++) {          char Agene[101] = "";          char Bgene[101] = "";          // printf("%d\n", (int)sizeof(DPResult));          for (int i = 0; i < 101; i++) {              for (int j = 0; j < 101; j++) {                  DPResult[i][j] = 9999;                              }          }          // memset(DPResult, 9999, sizeof(DPResult));          int ALength = 0;          int BLength = 0;          scanf("%d %s", &ALength, Agene);          scanf("%d %s", &BLength, Bgene);          printf("%d\n", getMaxSimilarity(Agene, Bgene, 0, 0));      } }

其实就是ＬＣＳ只是一个变种，为了提高效率，　存储类似矩阵的空间被浪费了。

２Ｂ一开始，我只记得写递归(我试着把它交给ＤＰ第二种写法，　有需要的时候求值，求完值存储，　而不是之前开始遍历循环， 以后再用循环做一次)

，忘记存储，结果ＴＬＥ。对ＤＰ重叠子问题的优化更令人印象深刻.

这个问题的描述　两个 '-' 两者之间无法比较，　事实上，递归的结束条件，等到两个gene都没有非'-'字符比较时，就不能两个都加'-'，　所以即使结束了.

递归效率不如直接数组高，　但有时更容易理解，但有时更容易理解.

还犯了低级错误，试图使用它ｍｅｍｓｅｔint数组的初始化，　但是ｍｅｍｓｅｔ每一个都是初始化的 [字节]为Ａ，　那么对于ｉｎｔ(四字节)，　最终值变成了四个值的字节位（ＡＡＡＡ）加来的值。