DP-最长公共子序列

题面：

样例：

思路：

这里我们状态表示确实比较奇怪，两个序列用二维来表示比较好想，但是这个表示的意义就记住吧hhh。这里比较难想的是状态划分，既然我们想要用前面的来表示后面的（也就是说要用到到推思想）那我们就从到底选不选第一个序列的第i个数以及第二个序列的第j个数来分类。这里一开始划分的时候没想到同时选i,j有一个先决条件。就是这两个数字必须相等，所以我们对a[i],b[j]是否相等来划分序列。

代码： #include<iostream> #include<string> using namespace std; const int N = 1010; int n,m; char a[N],b[N]; int f[N][N]; int main(void) { cin >> n >> m; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i <= m;i++) cin >> b[i]; //if(a[1] == b[1]) f[1][1] = 1; for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) { f[i][j] = max(f[i][j-1],f[i-1][j]); if(a[i] == b[j]) { f[i][j] = max(f[i][j],f[i-1][j-1]+1); } //这里其实可以不写else else { f[i][j] = max(f[i][j],f[i-1][j-1]); } } cout << f[n][m] << endl; return 0; } tips:

其实自己在想的时候默认选i不选j这种情况就是f[i][j-1],实则不然，f[i][j-1]这个集合是包含了选i不选j这种情况的（选i不选j是小于f[i][j-1]这个集合的），但是这里在这道题里面是不影响的，我们求的是最长值，并不是计算数量的问题，重复了也无所谓。同样我们在算f[i-1][j-1]的时候也是没必要计算的。而且忘记了max只能两个参数hhh。