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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

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]
		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):
		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))
		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')
				if A[index] > A[index - 1] and B[index] > B[index - 1]:
					ans = min(ans, rec(index + 1, 0))
				if A[index] > B[index - 1] and B[index] > A[index - 1]:
					(A[index], B[index]) = (B[index], A[index])
					ans = min(ans, 1 + rec(index + 1, 1))
					(A[index], B[index]) = (B[index], A[index])
				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) = ([_ 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]:
				swap[i] = min(swap[i], keep[i - 1] + 1)
				keep[i] = min(keep[i], swap[i - 1])
		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])