题解 | #牛群间的最大配对#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums1 int整型vector
     * @param nums2 int整型vector
     * @return int整型
     */
    int maxUncrossedMatch(vector<int>& nums1, vector<int>& nums2) {
        // init
        f.resize(nums1.size(), vector<int>(nums2.size(), -1));
        for (auto p : nums1) n1.push_back(p);
        for (auto p : nums2) n2.push_back(p);
        // write code here
        return dfs(n1.size() - 1, n2.size() - 1);
    }

    // 记忆化搜索
    int dfs(int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (f[i][j] != -1) return f[i][j];
        if (n1[i] == n2[j]) {
            f[i][j] = dfs(i - 1, j - 1) + 1;
        } else {
            f[i][j] = max(dfs(i - 1, j), dfs(i, j - 1));
        }
        return f[i][j];
    }

    vector<int> n1, n2;
    vector<vector<int> > f;
    // f[i][j]: n1 前 i 位与 n2 前 j 位的最大公共子序列长度
    // f[i][j] = f[i - 1][j - 1] + 1, if n1[i] == n2[j]
    // f[i][j] = max(f[i - 1][j], f[i][j - 1]), else
};

最长公共子序列