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