题目解析
这道题是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(); } };
|