LeetCode1035. 不相交的线(二维动态规划)

题目

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足： nums1[i] == nums2[j]. 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如下图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

解答

问题花里胡哨说了一堆，究其本质，其实是求解数组 nums1和 nums2的最长公共子序列的长度。
给定两个数组 nums1和 nums2，当 $nums1\left[i\right]==nums2\left[j\right]$时，可以用一条直线连接 nums1[i]和nums2[j]。假设一共绘制了 k 条互不相交的直线，其中第 x 条直线连接 $nums1\left[i_x\right]$和$nums2\left[j_x\right]$，则对于任意 $1<x<k$都有 $nums1\left[i_x\right]==nums2\left[j_x\right]$，其中 $i_1<i_2<i_k$, $j_1<j_2<j_k$。上述 k 条互不相交的直线分别连接了数组 nums1 和 nums 2的 k 对相等的元素，而且这 k 对相等的元素在两个数组中的相对顺序是一致的，因此，这 k 对相等的元素组成的序列即为数组 nums1 和 nums2的公共子序列。

求解公共子序列是典型的二维动态规划问题。
假设数组 nums1和 nums2 的长度分别为 m 和 n，创建 m+1 行 n+1 列的二维数组 dp，其中 $dp\left[i\right]\left[j\right]$表示$nums1\left[0:1\right]$和 $nums2\left[0:j\right]$的最长公共子序列的长度。$nums1\left[0:1\right]$表示数组 nums1 的长度为 i 的前缀；$nums2\left[0:j\right]$表示数组 nums2 的长度为 j 的前缀。

• 先考虑边界情况
  • 当 $i=0$ 时，$nums1\left[0:i\right]$ 为空，空数组和任何数组的最长公共子序列的长度都是 0，因此对任意 $0<=j<=n$有$dp\left[0\right]\left[j\right]==0$；
  • 当$j=0$ 时，$nums2\left[0:j\right]$ 为空，同理可得，对任意 $0<=i<=m$有$dp\left[i\right]\left[0\right]==0$；
• 当$i>0,j>0$时，考虑$dp\left[i\right]\left[j\right]$的计算：
  • $nums1\left[i-1\right]==nums2\left[j-1\right]$时，$dp\left[i\right]\left[j\right]==dp\left[i-1\right]\left[j-1\right]+1$
  • $nums1\left[i-1\right]!=nums2\left[j-1\right]$时，$dp\left[i\right]\left[j\right]==max(dp\left[i-1\right]\left[j\right],dp\left[i\right]\left[j-1\right])$

代码：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            int num1 = nums1[i - 1];
            for (int j = 1; j <= n; j++) {
                int num2 = nums2[j - 1];
                if (num1 == num2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20