DNA分子是以4种脱氧核苷酸为单位连接而成的长链，这4种脱氧核苷酸分别含有A,T,C,G四种碱基。碱基互补配对原则：A和T是配对的，C和G是配对的。如果两条碱基链长度是相同的并且每个位置的碱基是配对的，那么他们就可以配对合成为DNA的双螺旋结构。现在给出两条碱基链，允许在其中一条上做替换操作：把序列上的某个位置的碱基更换为另外一种碱基。问最少需要多少次让两条碱基链配对成功
输入描述:
输入包括一行： 包括两个字符串,分别表示两条链,两个字符串长度相同且长度均小于等于50。
输出描述:
输出一个整数，即最少需要多少次让两条碱基链配对成功
输入例子1:
ACGT TGCA
输出例子1:
0算法：动态规划
#include<iostream>
#include<
string>
#include<algorithm>
using namespace std;
bool issame(
char a,
char b){
return abs((a-
'0')-(b-
'0'))==
19||abs((a-
'0')-(b-
'0'))==
4;
}
int dp(
string& s,
string&
t){
int n=
s.size();
vector<vector<
int>>f(n+
1,vector<
int>(n+
1));
for(
int i=
0;i<=n;i++)f[
0][i]=i,f[i][
0]=
i;
for(
int i=
1;i<=n;i++
)
for(
int j=
1;j<=n;j++
){
f[i][j]=f[i-
1][j-
1]+(!issame(s[i-
1],t[j-
1]));
}
return f[n][n];
}
int main(
void){
string s,t;
cin>>s>>
t;
int n=
s.size();
cout<<dp(s,t)<<
endl;
return 0;
}
转载于:https://www.cnblogs.com/programyang/p/11189749.html
相关资源：紫外激光束对Salmonella typhimurium中的DNA合成和退化的作用
