Java O(n) DP Solution
swapRecord means for the ith element in A and B, the minimum swaps if we swap A[i] and B[i]\nfixRecord means for the ith element in A and B, the minimum swaps i
```swapRecord``` means for the ith element in A and B, the minimum swaps if we swap ```A[i]``` and ```B[i]```\n```fixRecord``` means for the ith element in A and B, the minimum swaps if we DONOT swap ```A[i]``` and ```B[i]```\n```\nclass Solution {\n    public int minSwap(int[] A, int[] B) {\n        int swapRecord = 1, fixRecord = 0;\n        for (int i = 1; i < A.length; i++) {\n            if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) {\n\t\t// In this case, the ith manipulation should be same as the i-1th manipulation\n                // fixRecord = fixRecord;\n                swapRecord++;\n            } else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) {\n\t\t// In this case, the ith manipulation should be the opposite of the i-1th manipulation\n                int temp = swapRecord;\n                swapRecord = fixRecord + 1;\n                fixRecord = temp;\n            } else {\n                // Either swap or fix is OK. Let\'s keep the minimum one\n                int min = Math.min(swapRecord, fixRecord);\n                swapRecord = min + 1;\n                fixRecord = min;\n            }\n        }\n        return Math.min(swapRecord, fixRecord);\n    }\n}\n```\n\nLet me firstly explain the O(n) space DP solution which uses swapRecord[n] and fixRecord[n]. It would be more explicit.\n\nOne thing should be kept in mind is, the array A and B would always be valid after you do the swap manipulation or not for each element. Take an example:\n\n```\nindex               0    1    2    3    4\nA                   1    3    5    4    9\nB                   1    2    3    7    10   \nswapRecord          1    1    2    1    2\nfixRecord           0    0    0    2    1\n```\n\n```swapRecord[i]``` means for the ith element in A and B, the minimum swaps if we swap A[i] and B[i]\n```fixRecord[i]``` means for the ith element in A and B, the minimum swaps if we DONOT swap A[i] and B[i]\n\nObviously, ```swapRecord[0] = 1``` and ```fixRecord[0] = 0```.\n\nFor ```i = 1```, either swap or fix is OK. So we take the minimum previous result, ```min = min(swapRecord[0], fixRecord[0]) = 0```. ```swapRecord[1] = min + 1 = 1```, ```fixRecord[1] = min = 0```\nFor ```i = 2```, notice that A[1] >= B[2], which means the manipulation of ```A[2] and B[2]``` should be same as ```A[1] and B[1]```, if A[1] and B[1] swap, A[2] and B[2] should swap, vice versa. Make sense, right? So ```swapRecord[2] = swapRecord[1] + 1``` and ```fixRecord[2] = fixRecord[1]```\nFor ```i = 3```, notice that A[2] >= A[3], which mean the manipulation of ```A[3] and B[3]``` and ```A[2] and B[2]``` should be opposite. In this case, ```swapRecord[3] = fixRecord[2] + 1``` and ```fixRecord[3] = swapRecord[2]```\nFor the last elements, it\'s similiar as the elements when i = 1. Either swap or fix is OK. You can try to figure this out. :D\n\nFinally, we get the minimum of last swapRecord and fixRecord. It should be the result.\n\nNotice that every ith swapRecord and fixRecord is only relevant with the previous one. So the algorithm should be optimized to an O(1) space version. Just like the code I write above.
[]