不相交的线 图解题解

这道题到底在问什么

输入

nums1=[1,4,2], nums2=[1,2,4]

输出

2 （连 1-1 与 4-4，再连 2-2 就会和 4-4 交叉）

输入

nums1=[1,2,4], nums2=[1,2,4]

输出

3 （三个数顺序完全一致，全连上）

最优解：一步一步想明白

1. 3记住这套「相等取左上加一，不相等取上、左较大」，下面每填一格都在套它。
2. 4先搭表。行头是 nums1=[1,4,2]，列头是 nums2=[1,2,4]，最上一行和最左一列代表「一边为空」，连不出线，全部填 0（蓝色）。接下来从左上往右下一格格填内部。
3. 5填 [1,1] 这格：nums1 的 1 和 nums2 的 1 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。
4. 6左上角是 0，加上新连的这一条 = 1。这格落子 1（绿色）。
5. 7填 [1,2] 这格：nums1 的 1 和 nums2 的 2 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
6. 8上面是 0，左边是 1，取较大 = 1。这格落子 1（绿色）。
7. 9填 [1,3] 这格：nums1 的 1 和 nums2 的 4 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
8. 10上面是 0，左边是 1，取较大 = 1。这格落子 1（绿色）。
9. 11填 [2,1] 这格：nums1 的 4 和 nums2 的 1 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
10. 12上面是 1，左边是 0，取较大 = 1。这格落子 1（绿色）。
11. 13填 [2,2] 这格：nums1 的 4 和 nums2 的 2 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
12. 14上面是 1，左边是 1，取较大 = 1。这格落子 1（绿色）。
13. 15填 [2,3] 这格：nums1 的 4 和 nums2 的 4 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。
14. 16左上角是 1，加上新连的这一条 = 2。这格落子 2（绿色）。
15. 17填 [3,1] 这格：nums1 的 2 和 nums2 的 1 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
16. 18上面是 1，左边是 0，取较大 = 1。这格落子 1（绿色）。
17. 19填 [3,2] 这格：nums1 的 2 和 nums2 的 2 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。
18. 20左上角是 1，加上新连的这一条 = 2。这格落子 2（绿色）。
19. 21填 [3,3] 这格：nums1 的 2 和 nums2 的 4 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
20. 22上面是 2，左边是 2，取较大 = 2。这格落子 2（绿色）。
21. 23表填满了。右下角 dp[3][3] = 2，就是最多能连出的线数。
22. 24回看哪几步是「相等加一」：整张表其实有三格——[1,1] 连 1-1、[2,3] 连 4-4、[3,2] 连 2-2，都是踩着左上角加一长出来的。但 [2,3](4-4) 和 [3,2](2-2) 这两条会交叉，只能二选一；这条最优连线选了 [1,1] 和 [2,3] 两格（橙色），第三格 [3,2]（蓝色）连上就会和 4-4 撞，所以最多仍是 2 条。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i, x in enumerate(nums1, 1):
            for j, y in enumerate(nums2, 1):
                if x == y:
                    f[i][j] = f[i - 1][j - 1] + 1
                else:
                    f[i][j] = max(f[i - 1][j], f[i][j - 1])
        return f[m][n]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[m][n];
    }
};

import java.util.*;
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[m][n];
    }
}

复杂度

面试官可能追问