当x = 0 或 y = 0时 f[x][y] = 0
当a[x] = b[y]时 f[x][y] = f[x-1][y-1]+1
当a[x] ！= b[y]时 f[x][y] = max(f[x][y-1], f[x-1][y])
注意这里字符串要从1开始，因为转移方程里面0表示这个字符串为空的时候。
动态规划涉及到字符串最好从1开始
还有就是路径的问题，可以把二维数组画出来，推出转移的方向。
这个方法我还是第一次见，很牛逼。
#include<cstdio>
#include<cstring>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
char a[MAXN], b[MAXN];
int f[MAXN][MAXN], pre[MAXN][MAXN];void print(int x, int y)
{if(pre[x][y] == 1){ print(x - 1, y - 1);putchar(a[x]);}else if(pre[x][y] == 2) print(x - 1, y);else if(pre[x][y] == 3) print(x, y - 1);
}int main()
{scanf("%s%s", a + 1, b + 1);int n = strlen(a + 1), m = strlen(b + 1);REP(i, 1, n + 1)REP(j, 1, m + 1){if(a[i] == b[j]){f[i][j] = f[i - 1][j - 1] + 1;pre[i][j] = 1;}else{if(f[i - 1][j] > f[i][j - 1]){f[i][j] = f[i - 1][j];pre[i][j] = 2;}else{f[i][j] = f[i][j - 1];pre[i][j] = 3;}}}print(n, m);puts("");return 0;
}