C++备忘录方法求最长子序列代码

以下是使用备忘录方法求最长子序列的C++代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1000;
int memo[MAXN][MAXN];

int LCS(string s1, string s2, int i, int j) {
    if (i == 0 || j == 0) {
        return 0;
    }
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    if (s1[i-1] == s2[j-1]) {
        memo[i][j] = LCS(s1, s2, i-1, j-1) + 1;
    } else {
        memo[i][j] = max(LCS(s1, s2, i-1, j), LCS(s1, s2, i, j-1));
    }
    return memo[i][j];
}

int main() {
    string s1 = "ABCDGH";
    string s2 = "AEDFHR";
    memset(memo, -1, sizeof(memo));
    cout << "Length of LCS is " << LCS(s1, s2, s1.length(), s2.length()) << endl;
    return 0;
}

这里使用了一个二维数组memo来记录已经计算过的子问题的解，避免重复计算。函数LCS递归地调用自己来求解子问题的解，如果在memo中已经有了子问题的解，则直接返回该解，否则进行计算并将结果存入memo中。最终输出LCS的长度。