801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.

Note:

• A, B are arrays with the same length, and that length will be in the range [1, 1000].

• A[i], B[i] are integer values in the range [0, 2000].

swap[i]: the minimum swaps if A[i] is swapped with B[i] fix[i]: the minimum swaps if A[i] and B[i] are fixed (1) if A[i - 1] < A[i] and B[i - 1] < B[i] and A[i - 1] < B[i] and B[i - 1] < A[i], swap[i] = min(swap[i - 1], fix[i - 1]) + 1, fix[i] = min(fix[i - 1], swap[i - 1]) (2) if A[i - 1] >= B[i] or B[i - 1] >= A[i], the manipulation of A[i] and B[i] should be same as the one of A[i - 1] and B[i - 1], swap[i] = swap[i - 1] + 1, fix[i] = fix[i - 1] (3) if A[i - 1] >= A[i] or B[i - 1] >= B[i], the manipulation of A[i] and B[i] should be opposite to the one of A[i - 1] and B[i - 1], swap[i] = fix[i - 1] + 1, fix[i] = swap[i - 1]

// Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(n)
    int n = A.size();
    vector<int> swap(n), fix(n);
    swap[0] = 1;
    for (int i = 1; i < n; ++i) {
        if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) { // (2) same as the previous manipulation
            swap[i] = swap[i - 1] + 1;
            fix[i] = fix[i - 1];
        } else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) { // (3) oppotite to the previous manipuliation
            swap[i] = fix[i - 1] + 1;
            fix[i] = swap[i - 1];
        } else { // (1) either swap or fix is okay
            int mn = min(swap[i - 1], fix[i - 1]);
            swap[i] = mn + 1;
            fix[i] = mn;
        }
    }
    return min(swap.back(), fix.back());
}

// Space Optimized Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(1)
    int n = A.size(), swap = 1, fix = 0;
    for (int i = 1; i < n; ++i) {
        if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) { // same as the previous manipulation
            swap = swap + 1;
            // fix = fix;
        } else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) { // oppotite to the previous manipuliation
            // int tmp = swap;
            // swap = fix + 1;
            // fix = tmp;
            std::swap(swap, fix);
            swap += 1;
        } else { // either swap or fix is okay
            int mn = min(swap, fix);
            swap = mn + 1;
            fix = mn;
        }
    }
    return min(swap, fix);
}

下面是另外一種DP的想法，分為兩種情形，一種是(i - 1)和i位置上的數字已經排好序，如果要swap的話就一定要(i - 1)和i都swap; 另一種是(i - 1)和i位置上的數字在(i - 1)或i交換之後會變成有序增加。

// Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(n)
    int n = A.size();
    vector<int> swap(n, n), fix(n, n);
    swap[0] = 1; 
    fix[0] = 0;
    for (int i = 1; i < n; ++i) {
        // Already increasing in [i - 1, i]
        if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
            swap[i] = swap[i - 1] + 1;
            fix[i] = fix[i - 1];
        }
        // Will be increasing in [i - 1, i] after swapping (i - 1) or i
        if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
            swap[i] = min(swap[i], fix[i - 1] + 1);
            fix[i] = min(fix[i], swap[i - 1]);
        }
    }
    return min(swap.back(), fix.back());
}

// Dynamic Programming
int minSwap(vector<int>& A, vector<int>& B) { // time: O(n); space: O(1)
    int n = A.size(), swap1 = 1, fix1 = 0;
    for (int i = 1; i < n; ++i) {
        int swap2 = numeric_limits<int>::max(), fix2 = numeric_limits<int>::max();
        if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
            swap2 = swap1 + 1;
            fix2 = fix1;
        }
        if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
            swap2 = min(swap2, fix1 + 1);
            fix2 = min(fix2, swap1);
        }
        swap1 = swap2;
        fix1 = fix2;
    }
    return min(swap1, fix1);
}