LEETCODE 1035. Uncrossed Lines 解题思路分析

题目大意：

不相交的线

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

示例 1：

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

示例 2：

输入：A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出：3

示例 3：

输入：A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出：2

提示：

1. 1 <= A.length <= 500
2. 1 <= B.length <= 500
3. 1 <= A[i], B[i] <= 2000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1035

解题思路分析：

这时一道动态规划类型的题目。因此也可以使用递归加记忆数组的方式来解题。本文我们采用递归方法为例来做讲解。

先建立一个递归方法，方法的参数中需要分别定义两个数组当前的下标。函数的返回值为当前下标到数组末尾间两个数组间能够绘制出的最大连线数。初始时，两个数组的下标均在0处。递归函数中，对于当前两个下标，我们可以做出三种选择：

1. 不做出连线，将A数组下标加一后递归至子问题。
2. 不做出连线，将B数组下标加一后递归至子问题。
3. 如果两个下标对应的数字相同，我们做出连线（连线数加一），然后将A和B的下标同时加一再递归至子问题。（这里解释一下下标加一的目的，如果在当前两个下标间做出连线，那么其他的连线不可能交叉此线段连接到当前2个下标左边的位置，也就是说其他连线的位置不会小于等于当前两个下标的位置。因此为了避免交叉线的出现，我们将连线后的下标加一传入子递归问题）

上述三种情况的最大值，即为当前递归的返回值。

最后再考虑记忆数组，由于递归函数中存在2个可变参数（A和B数组的当前下标），因此我们需要建立一个2维数组来记录当前递归的结果。

实现代码：

Integer[][] memo;
public int maxUncrossedLines(int[] A, int[] B) {
    // 初始化记忆数组
    memo=new Integer[A.length][B.length];
    // 递归求解
    return help(A,B,0,0);
}

int help(int[] A, int[] B, int ia, int ib){
    // 如果下标越界，结束递归
    if(ia==A.length||ib==B.length) return 0;
    // 如果记忆数组中存在当前解，直接返回。
    if(memo[ia][ib]!=null) return memo[ia][ib];
    int max=0; // 返回值
    // 将B下标加一递归至子问题
    max=Math.max(max,help(A,B,ia,ib+1));
    // 将A下标加一递归至子问题
    max=Math.max(max,help(A,B,ia+1,ib));
    // 如果当前两个数字相同，可以连线
    if(A[ia]==B[ib]){
        // 连线后，将A和B的下标同时加一，递归至子问题。
        max=Math.max(max,1+help(A,B,ia+1,ib+1));
    }
    memo[ia][ib]=max;
    return max;
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 20.20% of Java online submissions for Uncrossed Lines.

Memory Usage: 39.2 MB, less than 6.33% of Java online submissions for Uncrossed Lines.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1035-uncrossed-lines-解题思路分析/