常用算法
1、DP（动态规划）
/*1080-HumanGeneFunctions.cpp*/
观察题目给出的一个最优解：
AGTGATG
-GTTA-G
将其从某一处切开，如果左边部分的分值不是最大，那么将其进行调整，使其分值变大，
则整个解分值变大，与已知的最优矛盾。所以左边部分的分值必是最大。
同理，右边也是。可见满足最优子结构的性质。考虑使用 DP：
设两个 DNA 序列分别为 s1，s2，长度分别为 len1，len2，score 为分值表。
f[i,j]表示子串 s1[1..i]和 s2[1..j]的分值。考虑一个 f[i,j]，我们有：
1.s1 取第 i 个字母，s2 取“-”：f[i-1,j] + score[s1[i],''-'']
2.s1 取“-”，s2 取第 j 个字母：f[i,j-1] + score[''-'',s2[j]]
3.s1 取第 i 个字母，s2 取第 j 个字母：f[i-1,j-1] + score[s1[i],s2[j]]
即 f[i,j] = max(f[i-1,j] + score[s1[i],''-''], f[i,j-1] + score[''-'',s2[j]], f[i-1,j-1] +
score[s1[i],s2[j]]);
然后考虑边界条件，这道题为 i 或 j 为 0 的情况。
当 i=j=0 时，即为 f[0,0]，这是在计算 f[1,1]时用到的，根据 f[1,1] = f[0,0] +
score[s1[i], s2[j]]，明显有 f[0,0] = 0。
当 i=0 时，即为 f[0,1..len2]，有了 f[0,0]，可以用 f[0,j] = f[0,j-1] + table[''-'',s2[j]]来
计算。
当 j=0 时，即为 f[1..len1,0]，有了 f[0,0]，可以用 f[i,0] = f[i-1,0] + table[s1[i],''-'']来
计算。
至于计算顺序，只要保证计算 f[i,j]的时候，使用到的 f[i-1,j]，f[i,j-1]，f[i-1,j-1]都计算出来
了就行了。
所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重循环就可以了。*/
#include
#include
#include
using namespace std;
#define MAX(a,b,c) (a>b?a:b)>c?(a>b?a:b):c
int ctoi(char a){
int b;
if(a==''A'') b = 0;
if(a==''C'') b = 1;
if(a==''G'') b = 2;
if(a==''T'') b = 3;
if(a==''-'') b = 4;
return b;
}
int main()
{
int t,j,k,m,n;
评论0