【Leetcode】1035. Uncrossed Lines

题目地址：

https://leetcode.com/problems/uncrossed-lines/description/

给定两个数组$A$和$B$，想象将两个数组排成两行并且左对齐，求一种两个数组的数字之间的连线方式，使得连线互不相交，并且连接的两个数字都相等。

其实就是求最长公共子序列长度，可以动态规划。代码如下：

class Solution {
 public:
  int maxUncrossedLines(vector<int>& a, vector<int>& b) {
    int m = a.size(), n = b.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++)
        f[i][j] = a[i - 1] == b[j - 1] ? 1 + f[i - 1][j - 1]
                                       : max(f[i - 1][j], f[i][j - 1]);

    return f[m][n];
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时空复杂度$O(l_A{l}_B)$。