801. Minimum Swaps To Make Sequences Increasing

DP

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