สมมติว่าเราเขียนจำนวนเต็มของ A และ B (ตามลำดับที่กำหนด) ในเส้นแนวนอนสองเส้นแยกกัน ตอนนี้ เราอาจวาดเส้นเชื่อม:เส้นตรงที่เชื่อมตัวเลขสองตัว A[i] และ B[j] ในลักษณะที่ว่า −
-
A[i] ==B[j];
-
เส้นที่เราวาดซึ่งไม่ตัดกับเส้นเชื่อมต่ออื่น (ไม่ใช่แนวนอน)
เราต้องจำไว้ว่าเส้นเชื่อมต่อไม่สามารถตัดกันได้แม้ที่จุดปลาย - แต่ละหมายเลขสามารถอยู่ในสายเชื่อมต่อเดียวเท่านั้น ค้นหาจำนวนสายเชื่อมต่อสูงสุด ดังนั้นหากอินพุตเป็น [1,4,2] และ [1,2,4] ผลลัพธ์จะเป็น 2
| 1 | 4 | 2 |
| 1 | 2 | 4 |
เราสามารถวาดเส้นที่ไม่ขีดเส้น 2 เส้นดังในแผนภาพ เราไม่สามารถลากเส้นที่ไม่ผ่าน 3 เส้นได้ เนื่องจากเส้นจาก A[1]=4 ถึง B[2]=4 จะตัดกับเส้นจาก A[2]=2 ถึง B[1]=2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดวิธีการที่เรียกว่าแก้ปัญหา () ซึ่งจะใช้เวลา i, j, อาร์เรย์ A, อาร์เรย์ B และเมทริกซ์ dp
-
ถ้าฉันอยู่นอกช่วงอาร์เรย์ A ให้คืนค่า 0
-
ถ้า j อยู่นอกช่วงอาร์เรย์ B ให้คืนค่า 0
-
nj :=เจ
-
ในขณะที่ nj <ขนาดของ B และ B[nj] ไม่ใช่ A[i]
-
เพิ่ม nj ขึ้น 1
-
-
temp :=1 เมื่อ nj <ขนาดของ B มิฉะนั้น 0
-
ret :=สูงสุดของ (แก้ (i + 1, j, A, B, dp) และอุณหภูมิ) + แก้ปัญหา (i + 1, nj + 1, A, B, dp)
-
dp[i, j] :=ret และ return ret
-
จากวิธีหลัก
-
n :=ขนาดของ A, m :=ขนาดของ B
-
สร้างเมทริกซ์ขนาด dp n x m และเติมด้วย – 1
-
โทรแก้(0, 0, A, , dp)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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);
}
};
main(){
vector<int> v1 = {1,4,2};
vector<int> v2 = {1,2,4};
Solution ob;
cout << (ob.maxUncrossedLines(v1, v2));
} อินพุต
[1,4,2] [1,2,4]
ผลลัพธ์
2
