Số lần hoán vị tối thiểu để hai dãy tăng chặt trong C++

Mô tả bài toán

Cho hai dãy A và B cùng độ dài. Có thể hoán vị A[i] và B[i] tại cùng chỉ số. Tìm số hoán vị tối thiểu để cả hai dãy đều tăng chặt.

Ví dụ: A=[1,3,5,4], B=[1,2,3,7] → hoán vị chỉ số 3 → A=[1,3,5,7], B=[1,2,3,4] → kết quả 1.

Giải thuật Quy hoạch động

Giữ 2 trạng thái tại mỗi vị trí i:

• swap[i]: số hoán vị tối thiểu đến i nếu hoán vị tại i.
• noSwap[i]: số hoán vị tối thiểu đến i nếu KHÔNG hoán vị tại i.

Chuyển trạng thái:

• Nếu A[i] > A[i-1] && B[i] > B[i-1]: giữ nguyên trật tự → noSwap[i] = noSwap[i-1], swap[i] = swap[i-1] + 1.
• Nếu A[i] > B[i-1] && B[i] > A[i-1]: có thể hoán vị tại i hoặc i-1 → cập nhật chéo.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> swap(n, n), noSwap(n, n);
        swap[0] = 1; noSwap[0] = 0;
        for (int i = 1; i < n; i++) {
            if (A[i] > A[i-1] && B[i] > B[i-1]) {
                noSwap[i] = noSwap[i-1];
                swap[i] = swap[i-1] + 1;
            }
            if (A[i] > B[i-1] && B[i] > A[i-1]) {
                swap[i] = min(swap[i], noSwap[i-1] + 1);
                noSwap[i] = min(noSwap[i], swap[i-1]);
            }
        }
        return min(swap[n-1], noSwap[n-1]);
    }
};

int main() {
    vector<int> A = {1,3,5,4}, B = {1,2,3,7};
    Solution ob;
    cout << ob.minSwap(A, B); // 1
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(n) (có thể tối ưu xuống O(1)).