1. 题目来源
链接：1035. 不相交的线
相关：
- 不太相关：[线性dp] aw1012. 友好城市(最长上升子序列模型+思维)
- 强相关：[线性dp] aw897. 最长公共子序列(重要模板题+最长公共子序列模型)
- 弱相关：[线性dp] aw895最长上升子序列(知识理解+重要模板题+最长上升子序列模型+LCS转化LIS)
力赞题解，知识总结，对比 LCS 与 LIS 特性，深挖 LCS 状态分类，三叶姐yyds：
2. 题目解析
很有意思的一道题，不亏是小马AI，题单里的，哈哈。
一开始以为是做过的一道 思维+LIS，[线性dp] aw1012. 友好城市(最长上升子序列模型+思维)。看了看发现不是，然后就直接 dp 吧。然后发现和 lcs 思考过程一模一样…
做完之后看了三叶姐的题解，深受启发。 【宫水三叶の相信科学系列】求「最值问题」只需要确保「不漏」即可
- 时间复杂度： O ( n m ) O(nm) O(nm)。
- 空间复杂度： O ( n m ) O(nm) O(nm)
代码：
写法一：四种情况的分类划分，状态之间有重叠，但不影响最值。经典的 LCS 状态划分。
图片取自 传送门：【宫水三叶の相信科学系列】求「最值问题」只需要确保「不漏」即可。 强烈建议看看分析。再去看看 [线性dp] aw897. 最长公共子序列(重要模板题+最长公共子序列模型)。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (nums1[i - 1] == nums2[j - 1]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
return f[n][m];
}
};
写法二：LCS 的优化，仅判断 a[i]==b[j]，只分两种情况，状态转移加 if-else，代码结构与朴素版的一样。更加简洁。
其实经过仔细比对，会发现，当 a[i]==b[j] 时，状态一定由 f[i-1][j-1]+1 进行转移，就不需要通过 f[i][j] = max(f[i - 1][j], f[i][j - 1]); 这个转移了。但朴素的写法，会将这个放到前面，使其先判断不等，再判断相等。
重点理解：
- 其中，
a[i]==b[j]只需要f[i][j]=f[i-1][j-1]+1参与状态转移，而不需要其它的来进行大小比较。例如和四种状态划分一样，当a[i]==b[j]时，f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1)这三个值来比大小。以其中一个为例，f[i][j-1]相较于f[i-1][j-1]+1是多了一个a[i]元素的，那么如果这个a[i]元素匹配了b串中的某一个，也不过是+1的贡献量，顶多与f[i-1][j-1]+1持平。如果不匹配，甚至还不如f[i-1][j-1]+1，那么取max自然取不到它。 所以直接通过f[i][j]=f[i-1][j-1]+1进行状态转移。 - 所以，在
a[i]==b[j]状态转移时进行一个小优化。两种方法的代码实现将完全一致。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; 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[n][m];
}
};