0001 uint32_t lcsDP(const char* A, int n, const char* B, int m) {
0002    if (n < m) { swap(A, B);  swap(n, m); } //确保m<=n，以进一步节省空间
0003    uint32_t* lcs1 = new uint32_t[m+1]; //只需使用两个数组
0004    uint32_t* lcs2 = new uint32_t[m+1]; //交替滚动地记录最新的两行
0005    memset(lcs1, 0x00, sizeof(uint32_t)*(m+1));  lcs2[0] = 0; //递归基
0006    for (int i = 0; i < n; swap(lcs1, lcs2), i++) //逐行
0007       for (int j = 0; j < m; j++) //逐个解出子问题
0008          lcs2[j+1] = (A[i] == B[j]) ? lcs1[j] + 1 : max(lcs2[j], lcs1[j+1]);
0009    uint32_t solu = lcs1[m]; //原问题的解
0010    delete[] lcs1;  delete[] lcs2;  return solu;
0011 } //lcsDP