本文共 675 字，大约阅读时间需要 2 分钟。

注解

1、动态规划，最长公共子序列，三种情况：（不含空格，第一个字符含空格，第二个字符含空格）

dp[j][k] = max(dp[j][k], dp[j-1][k-1]+A[index][index2]);dp[j][k] = max(dp[j][k], dp[j-1][k]+A[index][4]);dp[j][k] = max(dp[j][k], dp[j][k-1]+A[4][index2]);

2、类似于最长公共子序列的做法。

代码

#include 
   
    #include 
    
     using namespace std;int A[5][5] = {
   {
   5, -1, -2, -1, -3},    {
   -1, 5, -3, -2, -4},    {
   -2, -3, 5, -2, -2},    {
   -1, -2, -2, 5, -1},    {
   -3, -4, -2, -1, -100}};string str = "ACGT";int main() {
       int T;    cin>>T;    for(int i=0; i
     
      >len1>>s1;        cin>>len2>>s2;        int dp[len1+1][len2+1];        memset(dp, 0, sizeof(dp));        for(int j=0; j
     
    
   

结果

转载地址：https://blog.csdn.net/zhanggirlzhangboy/article/details/103498336 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！