题目链接:https://www.lanqiao.cn/problems/1189/learning/
关于序列、子串这类问题挺多的,往往这些思想可以移植到别的地方,如一些dp或者贪心的题
这个题应该不是第一次做了,但还是没能做出来
dp的公式真是神奇而又巧妙== orz了
上代码
#include<bits/stdc++.h> using namespace std; #define ll long long ll n,m; ll a[1010]; ll b[1010]; ll dp[1010][1010]; int main() { ll i,j,ans=0; cin>>n>>m; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=m;i++) cin>>b[i]; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);//前面操作保留过的 if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);//保留的和计算的哪个大 } } cout<<dp[n][m]; }