32 lines
794 B
JavaScript
32 lines
794 B
JavaScript
/**
|
||
* @param {number[]} nums1
|
||
* @param {number[]} nums2
|
||
* @return {number}
|
||
*/
|
||
const maxUncrossedLines = function (nums1, nums2) {
|
||
|
||
};
|
||
|
||
/*
|
||
这个题看似无从下手实际上非常得简单，我们从结果入手，一个不交叉得最大连线是什么样的，经过观察发现就是要我们求
|
||
最大公共序列，直接把1143的题目拿过来改一下即可
|
||
*/
|
||
|
||
function f1(nums1, nums2) {
|
||
const m = nums1.length;
|
||
const n = nums2.length;
|
||
|
||
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
|
||
|
||
for (let i = m - 1; i >= 0; i--) {
|
||
for (let j = n - 1; j >= 0; j--) {
|
||
if (nums1[i] === nums2[j]) {
|
||
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[0][0];
|
||
}
|