Giả sử ta viết các số nguyên của mảng A và B (theo thứ tự cho trước) trên hai đường thẳng ngang riêng biệt. Ta có thể vẽ các đường nối: đường thẳng nối A[i] và B[j] sao cho:
A[i] == B[j];
Đường nối không cắt bất kỳ đường nối nào khác (không cắt nhau ngay cả tại đầu mút).
Tìm số lượng đường nối tối đa. Ví dụ: A = [1,4,2], B = [1,2,4], kết quả là 2.
Giải pháp dùng đệ quy có nhớ (memoization):
Định nghĩa hàm solve(i, j, A, B, dp)
Nếu i hoặc j vượt quá kích thước mảng, trả về 0
Tìm nj từ j sao cho B[nj] == A[i]
temp := 1 nếu tìm thấy, ngược lại 0
ret := max(solve(i+1, j), temp + solve(i+1, nj+1))
Lưu dp[i][j] = ret
Từ main: khởi tạo dp n x m với -1, gọi solve(0, 0, A, B, dp)
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int solve(int i, int j, vector <int>&A, vector <int>&B, vector < vector <int> >& dp){ if(i >= A.size()) return 0; if(j >= B.size()) return 0; if(dp[i][j] != -1) return dp[i][j]; int nj = j; while(nj < B.size() && B[nj] != A[i]) nj++; int ret = max(solve(i + 1, j, A, B, dp), (nj < B.size() ? 1 : 0) + solve(i + 1, nj + 1, A, B, dp)); return dp[i][j] = ret; } int maxUncrossedLines(vector<int>& A, vector<int>& B) { int n = A.size(); int m = B.size(); vector < vector <int > > dp(n, vector <int>(m, -1)); return solve(0, 0, A, B, dp); } }; int main(){ vector<int> v1 = {1,4,2}; vector<int> v2 = {1,2,4}; Solution ob; cout << (ob.maxUncrossedLines(v1, v2)); }Đầu vào
[1,4,2] [1,2,4]
Đầu ra
2