C++ 8ms 97% DP solution, O(n) time O(1) space w/ explanation
Took me a while to figure out the specific DP logic and mentally prove its correctness. The basic idea is this:\n\nAssume you arrive at index i of both arrays. 
Took me a while to figure out the specific DP logic and mentally prove its correctness. The basic idea is this:\n\nAssume you arrive at index `i` of both arrays. There are two things you can do. You can either keep `A[i]` and `B[i`] the way they are (do not flip them), or swap `A[i]` and `B[i]` (flip them). Of course there are restrictions. You can only keep (or flip) `A[i]`, `B[i]` if the result is *valid*. This means after either keeping or flipping the result should be: `A[i] > A[i-1] && B[i] > B[i-1]`. \n\nOther than the restriction of strictly increasing array, we also need to ensure we have the *minimum* number of swaps. So we have to choose the best option based on our previously calculated result. \n\nThe next step is to write out the DP logic based on what we can do:\n\nFirst we define two boolean quantities:\n\n`t1 = A[i] > A[i-1] && B[i] > B[i-1]`\n`t2 = A[i] > B[i-1] && B[i] > A[i-1]`\n\nCondition `t1` is true if the array is valid without flipping. Condition `t2` is true if the array is valid with flipping. It is important to notice that these two conditions are **not mutually exclusive**.  \n\nTo start off, we need two arrays, one remembering **minimum flips if we choose not to flip**, and the other **minimum flips if we choose to flip**. We will label them as `no_flip` and `flip`. `no_flip[i]` is defined as the number of moves required to make the arrays valid from `0 ... i`, and we do not flip at index `i`. `flip[i]` is defined as the number of moves required to make the arrays valid from `0 ... i`, but we *must* flip at index `i`. \n\n* **Assume at index `i` we do not want to flip.** What would be the required number of flips to make the arrays valid from `0 ... i` ?\nIf `t1` is true, then we don\'t have to do anything. Thus, the number of flips would be the same as those required from `no_flip[i-1]`.\nIf `t2` is true, then we *could* flip the previous pair `(A[i-1], B[i-1]`, whilethe arrays are still valid, so the number of flips required for that would be `flip[i-1]`. \nIf `t1` and `t2` are true, we have two options. Naturally, we pick the minimum, which would be `min(no_flip[i-1], flip[ i-1])`. If we only have one option, then we must choose that option. \nIf both options are invalid (guaranteed to not happen in this case), then we should put an arbitrary (large) number to indicate "impossible". \n\n* **Assume at index `i` we want to flip.** What would be the required number of flips to make the arrays valid from `0 ... i` ?\nIf `t1` is true, then we have an interesting scenario. We *must* flip at `i`, so then to be consistent with `t1` we need to also flip at `i-1`. Thus, the number of flips would be the same as those required from `flip[i-1]`.\nIf `t2` is true, since we are already flipping at `i` we do not flip at `i-1`, so the number of flips required for that would be `no_flip[i-1]`. \nIf `t1` and `t2` are true, we have two options. Naturally, we pick the minimum, which would be `min(flip[i-1], no_flip[i-1])`. If we only have one option, then we must choose that option. \nBecause we are flipping at index `i`, we need to **add 1** to our minimum flip count.\nIf both options are invalid (guaranteed to not happen in this case), then we should put an arbitrary (large) number to indicate "impossible". \n\nUsing this DP logic, our update rule is as follows:\n\n`no_flip[i-1] = t1 && t2 ? min(no_flip[i-1], flip[i-1]) : t1 ? no_flip[i-1] ; t2 ? flip[i-1] : 9001`\n`flip[i-1] = t1 && t2 ? 1 + min(flip[i-1], no_flip[i-1]) : t1 ? flip[i-1] ; t2 ? no_flip[i-1] : 9001`\n\nI used over 9000 as "impossible" here.\n\nTo begin, we have a single element which is always strictly sorted. Thus, `no_flip[0] = 0` and `flip[0] = 1`. `flip[0]` is 1 because the previous (empty array) is valid with 0 flips and we must flip at current index, which leads to `flip[0] = 0 + 1 = 1`.\n\nOnce we get values for `flip` and `no_flip` at the last index, we can simply take the minimum again to get the answer. This forms the DP solution for this problem, with run-time `O(n)` and space `O(n)`. \n\nTo convert the `O(n)` space DP solution to `O(1)` space, I combined the two required vectors (`no_flip` and `flip`) so that I keep the state of the previous iteration. In my code the vector `n` is defined as `n = {no_flip[i-1]. flip[i-1]}` and `other = {no_flip[i], flip[i]}`. \n\n**O(n) space**\n```\nclass Solution {\npublic:\n    int minSwap(vector<int>& A, vector<int>& B) {\n        int size = A.size(), count = 0;\n        vector<int> n(size, 0), f(size, 0); // n = no_flip, f = flip\n        f[0] = 1;\n        for(int i = 1; i < size; ++i) {\n            const bool t1 = A[i] > A[i-1] && B[i] > B[i-1], t2 = A[i] > B[i-1] && B[i] > A[i-1];\n            n[i] = t1 && t2 ? min(n[i-1], f[i-1]) : t1 ? n[i-1] : t2 ? f[i-1] : 9001;\n            f[i] = t1 && t2 ? 1 + min(n[i-1], f[i-1]) : t2 ? 1 + n[i-1] : t1 ? 1 + f[i-1] : 9001;\n        }     \n        return min(n.back(), f.back());\n    }\n};\n\nauto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();\n```\n\n\n**O(1) space** \n\n```\nclass Solution {\npublic:\n    int minSwap(vector<int>& A, vector<int>& B) {\n        int size = A.size(), count = 0;\n        vector<int> n(2, 0), other(2, 0); // index 0 = no_flip, index 1 = flip\n        n[1] = 1;\n        for(int i = 1; i < size; ++i) {\n            const bool t1 = A[i] > A[i-1] && B[i] > B[i-1], t2 = A[i] > B[i-1] && B[i] > A[i-1];\n            other[0] = t1 && t2 ? min(n[0], n[1]) : t1 ? n[0] : t2 ? n[1] : 9001;\n            other[1] = t1 && t2 ? 1 + min(n[0], n[1]) : t2 ? 1 + n[0] : t1 ? 1 + n[1] : 9001;\n            swap(n, other);\n        }     \n        return min(n[0], n[1]);\n    }\n};\n\nauto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();\n```
[]