【DNA序列还原】刷题
DNA序列还原
- 问题描述
- 输入描述:
- 输出描述:
- 思路
- 代码
#动态规划
问题描述
给定一段受损的 DNA 碱基序列 dna1,在每次只操作一个碱基的情况下,将其以最少的操作步骤将其还原到未受损的 DNA 碱基序列 dna2。
只可以对 DNA 碱基序列中的一个碱基进行三种操作:
- 增加一个碱基
- 去除一个碱基
- 替换一个碱基
输入描述:
输入两段 DNA 碱基序列,每段分一行输入
第一行为第一段受损的 DNA 碱基序列 dna1
第二行为第二段未受损的 DNA 碱基序列 dna2
输出描述:
最小操作步骤数
备注:
0 <= dna1.length, dna2.length <= 500
dna1 和 dna2 由大写英文字母 A、G、C、T 组成
示例 1
输入
AGCTTAGC
AGCTAGCT
输出
2
说明
AGCTTAGC -> AGCTAGC(删除 T)
AGCTAGC -> AGCTAGCT(增加 T)
示例 2
输入
AGCCGAGC
GCTAGCT
输出
4
说明
AGCCGAGC -> GCCGAGC(删除 A)
GCCGAGC -> GCTGAGC(将 C 替换为 T)
GCTGAGC -> GCTAGC(删除 G)
GCTAGC -> GCTAGCT(增加 T)
思路
-
动态规划方程 dp[i][j] 表示 字符串s1 的前i个元素 和 字符串s2的前j个元素 匹配的(最小代价)最小操作数
-
递推过程:
-
假设a是s1的前缀 ,b是s2的前缀,a->b的最小代价是dp[i][j]
-
那么 a+c->b的最小代价就是dp[i][j] = dp[i-1][j]+1
-
a->b+c的最小代价就是dp[i][j] = dp[i][j-1]+1
-
a+c->b+c的最小代价是 dp[i][j] = dp[i-1][j-1]
-
a+c->b+g的最小代价是 dp[i][j] = dp[i-1][j-1]+1
-
代码初始化也需要注意: 因为是求最小的操作数,所以在二维数据进行初始化的时候可以先填上最大值,在该题目中最大值可以取m+n, 因为这个是最大的操作数。其次,在第一列和第一行初始化的时候,最小的操作数就是当前指针指向的长度, 因为和空字符相比,“” 变换到“AGC” 操作数就是3, 就是i或者j的长度。
代码
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int solution(std::string dna1, std::string dna2) {
// Please write your code here
int m = dna1.length();
int n = dna2.length();
vector<vector<int>>dp(m+1,vector<int>(n+1));
//初始化
for(int i =0;i<m+1;i++){
for(int j=0;j<n+1;j++){
dp[i][j]=m+n;
}
}
//初始化
for(int i =0;i<m+1;i++){
dp[i][0]=i;
}
for(int j=0;j<n+1;j++){
dp[0][j]=j;
}
//遍历
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(dna1[i-1]== dna2[j-1]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=dp[i-1][j-1]+1;
}
dp[i][j]=min(dp[i-1][j]+1,dp[i][j]);
dp[i][j]=min(dp[i][j-1]+1,dp[i][j]);
}
}
return dp[m][n];
}
int main() {
// You can add more test cases here
std::cout << (solution("AGCTTAGC", "AGCTAGCT") == 2) << std::endl;
std::cout << (solution("AGCCGAGC", "GCTAGCT") == 4) << std::endl;
return 0;
}