[TyvjP1050] 最长公共子序列（DP）

f[i][j] 表示第 1 个串匹配到第 i 位，第 2 个串匹配到第 j 位的答案。

f[i][j] = max(f[i - 1][j], f[i][j - 1])　　　　　　　　　　 (a[i] != b[j])

f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1)　　(a[i] == b[j])

——代码

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using std::max;

 int n, m, f[][];

 char a[] = {''}, b[] = {''};

 int main()

 {

     int i, j;

     scanf("%s %s", a + , b + );

     n = strlen(a);

     m = strlen(b);

     for(i = ; i < n; i++)

         for(j = ; j < m; j++)

             if(a[i] == b[j]) f[i][j] = max(f[i - ][j - ] + , max(f[i - ][j], f[i][j - ]));

             else f[i][j] = max(f[i - ][j], f[i][j - ]);

     printf("%d", f[n - ][m - ]);

     return ;

 }

巴特西

[TyvjP1050] 最长公共子序列（DP）

最新文章

热门文章