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].

Difficulty: interview

Starter code:

class Solution:
    def minSwap(self, A: List[int], B: List[int]) -> int:
        

Solutions:
class Solution:
    def minSwap(self, A: List[int], B: List[int]) -> int:
        
        n = len(A)
        
        if n == 1:
            return 0
        
        dp = [[float('inf'), float('inf')] for _ in range(n)]
        dp[0] = [0,1] #[natural, swapped]
        
        for i in range(1, n):
            if A[i-1] < A[i] and B[i-1] < B[i]:
                dp[i] = [dp[i-1][0], dp[i-1][1]+1]
            if A[i-1] < B[i] and B[i-1] < A[i]:
                dp[i] = [min(dp[i][0],dp[i-1][1]), min(dp[i][1],dp[i-1][0]+1)]
                
        print(dp)
                

        return min(dp[-1])


class Solution:
    def minSwap(self, A, B):
        # 这道题是说A和B的swap是相对应的位置swap
        # index的遍历是同时遍历A和B的
        
        # 状态就是当前处理的是第几位 + 这一位是不是swap过来的
        #                 start^       swapped^
        return self._dfs(A, B, start=0, swapped=False, memo={})
    
    def _dfs(self, A, B, start, swapped, memo):
        if start == len(A):
            return 0
        
        key = (start, swapped)
        if key in memo:
            return memo[key]

        res = 2 ** 31 - 1
        prev_a = A[start - 1] if start > 0 else -2 ** 31 - 1
        prev_b = B[start - 1] if start > 0 else -2 ** 31 - 1
        
        if A[start] > prev_a and B[start] > prev_b:
            res = min(res, self._dfs(A, B, start + 1, False, memo))
        
        # 注意这里不能跳过
        # 否则会漏掉一些case
        if A[start] > prev_b and B[start] > prev_a:
            A[start], B[start] = B[start], A[start]
            res = min(res, self._dfs(A, B, start + 1, True, memo) + 1)
            A[start], B[start] = B[start], A[start]
        
        memo[key] = res
        return res

class Solution:
    def minSwap(self, A: List[int], B: List[int]) -> int:
        n=len(A)
        mem = {}
        def rec(index,ifSwapped):
            if index==n:
                return 0
            elif (index,ifSwapped) in mem:
                return mem[(index,ifSwapped)]
            else:
                ans=float('inf')
                #Don't swap if possible
                if A[index]>A[index-1] and B[index]>B[index-1]:
                    ans=min(ans,rec(index+1,0))
                #Swap if possible
                if A[index]>B[index-1] and B[index]>A[index-1]:
                    A[index],B[index]=B[index],A[index] #Swap
                    ans=min(ans,1+rec(index+1,1))
                    A[index],B[index]=B[index],A[index] #Swap them back
                mem[(index,ifSwapped)]=ans
                return ans
            
        ans=float('inf')
        ans=min(ans,rec(1,0))
        A[0],B[0]=B[0],A[0]
        ans=min(ans,1+rec(1,1))
        A[0],B[0]=B[0],A[0]
        
        return ans

class Solution:
    def minSwap(self, A: List[int], B: List[int]) -> int:
        
        no, yes, n = 0, 1, len(A)
        for i in range(1, n):
            no_u, yes_u = n, n
            if A[i-1] < A[i] and B[i-1] < B[i]:
                no_u, yes_u = no, yes + 1
            if A[i-1] < B[i] and B[i-1] < A[i]:
                no_u = min(no_u, yes)
                yes_u = min(yes_u, no+1)  
            
            no, yes = no_u, yes_u
        return min(no, yes)

class Solution:
    def minSwap(self, A: List[int], B: List[int]) -> int:
        N = len(A)
        not_swap, swap = 0, 1
        for i in range(1, N):
            not_swap2 = swap2 = N 
            if A[i - 1] < A[i] and B[i - 1] < B[i]:
                swap2 = swap + 1
                not_swap2 = not_swap
            if A[i - 1] < B[i] and B[i - 1] < A[i]:
                swap2 = min(swap2, not_swap + 1)
                not_swap2 = min(not_swap2, swap)
            swap, not_swap = swap2, not_swap2
        return min(swap, not_swap)

class Solution:
    def minSwap(self, A, B):
        N = len(A)
        #keep, swap = [0] * N, [0] * N
        #keep, swap = [N] * N, [N] * N
        keep, swap = [_ for _ in range(N)], [_ for _ in range(N)]
        swap[0] = 1                                      # important!
        for i in range(1, N):
            if A[i] > A[i-1] and B[i] > B[i-1]:
                keep[i] = keep[i-1]                      # keep, keep
                swap[i] = swap[i-1] + 1                  # swap, swap
            if A[i] > B[i-1] and B[i] > A[i-1]:
                swap[i] = min(swap[i], keep[i-1] + 1)    # keep, swap
                keep[i] = min(keep[i], swap[i-1])        # swap, keep
        return min(keep[-1], swap[-1])
    
class Solution:
    def minSwap(self, A, B):
        N = len(A)
        keep, swap = [_ for _ in range(N)], [_ for _ in range(N)]
        swap[0] = 1
        for i in range(1, N):
            if A[i] > A[i-1] and B[i] > B[i-1]:
                keep[i] = keep[i-1]
                swap[i] = swap[i-1] + 1
            if A[i] > B[i-1] and B[i] > A[i-1]:
                if keep[i-1] + 1 < swap[i]: swap[i] = keep[i-1] + 1
                if swap[i-1] < keep[i]: keep[i] = swap[i-1]
        return min(keep[-1], swap[-1])