题目描述：输入两个序列，输出它们的最长公共子序列

状态转移方程

A[i] = B[j], dp[i][j] = dp[i -1][j - 1] A[i] != B[j], dp[i][j] = max(d[i - 1][j], d[i][j - 1]) + 1

本来挺简单一段代码的，因为我DP数组定义在main里面导致一直段错误，直接报错，懵了个逼

代码

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int maxn = 110;
  8. int main(){
  9.     char A[maxn] = "sadstory", B[maxn] = "adminstory";
  10.     int dp[maxn][maxn] = {0};
  11.     int len_A = strlen(A + 1);
  12.     int len_B = strlen(B + 1);
  13.     for(int i = 0; i < max(len_A, len_B); i++){
  14.         dp[i][0] = dp[0][i] = 0;
  15.     }
  16.     for(int i = 1; i <= len_A; i++){
  17.         for(int j = 1; j <= len_B; j++){
  18.             if(A[i] == B[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
  19.             else {
  20.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  21.             }
  22.         }
  23.     }
  24.     printf("%d", dp[len_A][len_B]);
  25.     return 0;
  26. }