AcWing 897. 最长公共子序列

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 897. 最长公共子序列原题链接简单

作者：

yuechen , 2020-02-06 01:07:40 , 所有人可见 , 阅读 30844

504

223

问题分析

我觉得这题的状态分成两半考虑比较方便，按两个序列末尾的字符是不是相等来区分。
问题分析.PNG
如果两个字符相等，就可以直接转移到f[i-1][j-1]，不相等的话，两个字符一定有一个可以抛弃，可以对f[i-1][j],f[i][j-1]两种状态取max来转移。
状态转移.PNG

代码

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
  cin >> n >> m >> a + 1 >> b + 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) {
        f[i][j] = f[i - 1][j - 1] + 1;
      } else {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      }
    }
  }
  cout << f[n][m] << '\n';
  return 0;
}

105 评论

littleTurtle 2022-10-12 16:04

f[i][j] 表示在第一个序列的前i个字母中出现并且在第二个序列的前j个字母中出现的最大值
以第i个和第j个字母是否相同来划分
如果相同 f[i][j] = f[i - 1][j - 1] + 1
如果不相同 f[i][j] = max(f[i - 1][j], f[i][j - 1])
因为如果不相同，那么此时f[i][j]的值肯定不会大于f[i - 1][j]和f[i][j - 1]的最大值
那么一定会等于f[i - 1][j]和f[i][j - 1]的最大值
佬儿们，这样会不会好理解一点hh

哎呀这题该怎么暴力啊 2022-10-24 11:00

我不是佬，但我感觉没啥毛病hh

Pobz 2023-01-15 18:49

写的非常 #好

@WZ 2023-02-11 08:59

不明白为什么只有相同才可以{f[i][j] = f[i - 1][j - 1] + 1}，如果a[i]和b[j]都是公共子序列里面的，但是位置不同难道不能转移吗？
我写的是
{dp[i][j]=max(dp[i-1][j],dp[i][j]);
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
但是错了；
求大佬解答

Yxxx 2023-02-20 12:00 回复了 @WZ 的评论

比如a序列：abcde，b序列：bcdf，因为此时e与f不等，即a[5]!=b[4]
所以此时dp[5][4]=dp[4][3]，如果此时再dp[i][j] = dp[i - 1][j - 1] + 1就多加了

Mr.zhong 2023-04-01 18:41 回复了 Yxxx 的评论

秒

WhiteAlbum2 2023-09-02 10:47

而你就是我的英雄小turtle！

睡在树上的鱼 11个月前回复了 @WZ 的评论

a[i]和b[j]都是值，而不是位置，因为它们值不同所以不可能同时作为公共子序列的结尾

浅羽 7个月前

没毛病

Dong_2 7个月前

哇！太棒了！没有题解我怎么学啊˃̣̣̥᷄⌓˂̣̣̥᷅

Patek 6个月前回复了 @WZ 的评论

你对f[i][j]的理解错了，f[i][j]代表的是s1前i位和s2前j位的最长公共子序列，所以如果a[i]和b[j]都是f[i][j]的最长公共子序列里的，必定是f[i][j]的最长公共子序列的末尾元素。甚至有一个是最长公共子序列里的，必定也是f[i][j]的末尾元素，不会出现位置不同的情况。

霓虹小孩 3个月前

哎哟，这想法可以！

蓝路 2022-09-26 23:42

优雅

18768345098 2022-12-24 10:40

分成4块死活没看懂智商不够捏

Gaulle 2022-05-08 10:51

跟我想的一样，我也在思考那个if(a[i]==b[j])里，max有点多余

Listenhh 8个月前

牛哇，不愧是利维亚的杰洛特👍

s.. 7个月前

大佬们可以解答一下我这样为啥不能AC吗
#include[HTML_REMOVED]
#include[HTML_REMOVED]

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
scanf(“%d%d”, &n, &m);
//为啥这么写不对
for(int i = 1; i <= n; i ) scanf(“%c”, &a[i]);
getchar();
for(int i = 1; i <= m; i ) scanf(“%c”, &b[i]);

for(int i = 1; i <= n; i ++)
{
    for(int j = 1; j <= m; j ++)
    {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
    }
}

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

return 0;

}