Uncrossed Lines ใน C++

คำอธิบายปัญหา

มีตัวเลขสองแถว A และ B วาดเส้นเชื่อมระหว่าง A[i] และ B[j] ได้ก็ต่อเมื่อ A[i] == B[j] และเส้นไม่得以ตัดกัน (รวมถึงปลายเส้น) ต้องการหาจำนวนเส้นสูงสุดที่วาดได้

ตัวอย่าง: A=[1,4,2], B=[1,2,4] → ผลลัพธ์ 2

ข้อสังเกตสำคัญ

ปัญหานี้เทียบเท่ากับการหา Longest Common Subsequence (LCS) ของอาร์เรย์ทั้งสอง เพราะเงื่อนไข "ไม่ตัดกัน" หมายถึงลำดับต้องตรงกัน

วิธีแก้ปัญหา (DP แบบ Bottom-up)

1. สร้างตาราง dp ขนาด (n+1) × (m+1) เริ่มต้นเป็น 0
2. dp[i][j] = ความยาว LCS ของ A[0..i-1] และ B[0..j-1]
3. ถ้า A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1
4. มิฉะนั้น: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
5. คำตอบ = dp[n][m]

ตัวอย่างโค้ด C++ (Memoization)

#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() || 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 take = (nj < B.size()) ? 1 + solve(i+1, nj+1, A, B, dp) : 0;
        int skip = solve(i+1, j, A, B, dp);
        
        return dp[i][j] = max(take, skip);
    }
    
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int n = A.size(), 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);
    return 0;
}

อินพุต

[1,4,2] [1,2,4]

เอาต์พุต

2