动态规划３：最长公共子序列（不连续）

野性酷女 2023-07-09 02:11 110阅读 0赞 
  1. //最长公共子序列－－LCS
  3. #include <stdio.h>
  4. #include "cstring"
  5. #include "vector"
  6. #include "algorithm"
  8. using namespace std;
  9. const int N = 100;
  10. char A[N], B[N];
  11. int dp[N][N];//dp[i][j] A的i号位置与B的j号位置之前的LCS长度
  12. int main() { 
  13.     fgets(A + 1, N, stdin);//从１号位置开始
  14.     fgets(B + 1, N, stdin);
  15.     int lengthA = strlen(A + 1) - 1;
  16.     int lengthB = strlen(B + 1) - 1;
  17.     //边界
  18.     for (int i = 0; i <= lengthA; i++) { 
  19.         dp[i][0] = 0;
  20.     }
  21.     for (int j = 0; j <= lengthB; j++) { 
  22.         dp[0][j] = 0;
  23.     }
  24.     //状态转移方程
  26.     for (int i = 1; i <= lengthA; i++) { 
  27.         for (int j = 1; j <= lengthB; j++) { 
  29.             if (A[i] == B[j]) { 
  31.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  32.             } else { 
  33.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  35.             }
  36.         }
  38.     }
  39.     printf("%d\n", dp[lengthA][lengthB]);
  40.     return 0;
  41. }
  43. /* sadstory adminsorry */

测试结果：
在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读