请问为什么状态转移不能写成
if(a[i]==b[j])
f[i][j]=max(f[i-1][j]+1,f[i][j-1]+1);
//f[i][j]=max(f[i-1][j-1]+1,f[i][j]);
求解释+hack数据 谢谢!
全部代码:
#include <bits/stdc++.h>
using namespace std;
#define N 11455
int f[N][N];
int a[N];
int b[N];
int main() {
int n;
cin >> n;
for(int i =1;i<=n;i++){
cin>>a[i];
}
for(int i =1;i<=n;i++)cin>>b[i];
int ans = 0;
for(int i =1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i]==b[j]){
f[i][j]=max(f[i-1][j]+1,f[i][j-1]+1);
}else{
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
ans=max(ans,f[i][j]);
}
}
cout<<ans;
return 0;
}