题目解析

这道题是LCS(最长公共子序列)的数组版本,LCS资料都很多,本题的状态转移公式是:
dp[i][j] = dp[i-1][j-1]+1 while A[i] == B[j] or dp[i][j] = max(dp[i-1][j], dp[i][j-1]) while A[i] != B[j]

方法

时间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size(), vector<int>(B.size(), 0));

for (int i = 0; i < A.size(); i++) {
if (A[i] == B[0]) {
dp[i][0] = 1;
} else {
dp[i][0] = i == 0?0:dp[i-1][0];
}
}
for (int i = 0; i < B.size(); i++) {
if (B[i] == A[0]) {
dp[0][i] = 1;
} else {
dp[0][i] = i == 0?0:dp[0][i-1];
}
}

for (int i = 1; i < A.size(); i++) {
for (int j = 1; j < B.size(); j++) {
if (A[i] == B[j]) {
dp[i][j] = dp[i-1][j-1]+1;
} else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
}
return dp.back().back();
}
};