image.png

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const num1 = nums1[i - 1];
        for (let j = 1; j <= n; j++) {
            const num2 = nums2[j - 1];
            if (num1 === num2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};

这道题是最长公共子序列的长度的换皮，其实连换皮都不是，只是换了一种表达方式，那我们现在通过LCS(最长公共子序列)解析下

首先说明下这道题为啥是换皮，是由于题目中明确表示，绘制直线不与其他任何连线相交，连端点都不想交，那说明k 条互不相交的直线分别连接了数组 nums 1和 nums
2的 k 对相等的元素，而且这 k 对相等的元素在两个数组中的相对顺序是一致的（看示例会更明白）

image.png

这里是一张动态规划表，由此我们展开分析

首先设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共子序列记为LCS(X,Y)因为，我们需要找到X 和 Y中最长的那个公共子序列。而要找X 和 Y的LCS，首先考虑X的最后一个元素和Y的最后一个元素，那我们会遇到两种情况

1. 如果 xn=ym，即X的最后一个元素与Y的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS(Xn-1，Ym-1)
2. 如果xn != ym，那又会遇到两种情况

• LCS(Xn-1，Ym)表示：最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找
• LCS(Xn，Ym-1)表示：最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找
  求解上面两个子问题，得到的公共子序列谁最长，那谁就是 LCS（X,Y）。用数学表示就是：LCS=max{LCS(Xn-1，Ym)，LCS(Xn，Ym-1)}

最后借用一张图说明结论

image.png