Minimum swap to make sequence increasing

這道題拿到可以先想一下，對於一整個 array 要嚴格遞增，是不是可以透過 subarray 的嚴格遞增達到？

答案是可以，所以可以用 dp 來求解。

首先想到，我們在遍歷 A, B 時的所有交換可能是：1.(i-1), i 都交換，2.(i-1), i 都不交換，3.(i-1) 交換 i 不換，4.(i-1)不換 i 交換

第一種情況：1, 2 是在 A, B 都是嚴格遞增的情況下，也就是 A[i-1] < A[i] && B[i-1] < B[i]

第二種情況：在第一種情況之後，我們還可以看看是不是可以交換一邊就好，也就是當 A[i-1] < B[i] && B[i-1] < A[i] (題目保證 A[i-1] 不會同時大於 A[i], B[i])，這時就可以算交換一邊的 cost

所以我們需要兩個 array 來紀錄交換與不換，如果只用一個是無法儲存兩種結果

最後我們是比較 swap[n-1], notSwap[n-1] ，表示是都交換的最少還是不交換的最少

寫到一半我有個疑問是說 notSwap 結果好像都一直是 0 啊，那是要他幹嘛？但其實不是，因為在迴圈裡時，我們是每次都初始 n，在第二情況滿足下，他會跟 swap[i-1], notSwap[i] 比較，當 swap[i-1] 有值時，是會讓 notSwap[i] 變得不是 0，那下一個迴圈的第一情況，就有可能是用這個值去初始 notSwap[i] = notSwap[i-1]

反過來說，當 notSwap[i-1] 有值，表示的是前一次 「交換 i-1, i 不交換」這個情況

public int minSwap(int[] A, int[] B) {
    if (A == null || B == null || A.length == 0 || B.length == 0) {
        return 0;
    }
    int n = A.length;
    int swap[] = new int[n];
    int notSwap[] = new int[n];
    swap[0] = 1;
    notSwap[0] = 0;
    for (int i=1; i<n; i++) {
        swap[i] = notSwap[i] = n;
        if (A[i-1] < A[i] && B[i-1] < B[i]) {
            swap[i] = swap[i-1] + 1;
            notSwap[i] = notSwap[i-1];
        }
        if (A[i-1] < B[i] && B[i-1] < A[i]) {
            swap[i] = Math.min(notSwap[i-1]+1, swap[i]);
            notSwap[i] = Math.min(swap[i-1], notSwap[i]);
        } 
    }
    return Math.min(swap[n-1], notSwap[n-1]);
}