[Python] Top Down and Bottom Up DP Solutions
Top Down Expanded for Readability: 112 ms\npython\ndef minSwap(self, A: List[int], B: List[int]) -> int:\n\n\tif len(A) == 1: return 0\n\n\t@functools.lru_cache
**Top Down Expanded for Readability: 112 ms**\n```python\ndef minSwap(self, A: List[int], B: List[int]) -> int:\n\n\tif len(A) == 1: return 0\n\n\t@functools.lru_cache(None)\n\tdef helper(i, prev_swap):\n\n\t\tif i == len(A):\n\t\t\treturn 0\n\n\t\t# if the previous values (A[i-1] and B[i-1]) were swapped then a = B[i-1] and b = A[i-1]\n\t\ta,b = (B[i-1], A[i-1]) if prev_swap else (A[i-1], B[i-1])\n\n\t\toptions = []\n\n\t\t# don\'t swap A[i] and B[i]\n\t\tif A[i] > a and B[i] > b:\n\t\t\toptions.append(helper(i+1, False))\n\n\t\t# swap A[i] and B[i]\n\t\tif A[i] > b and B[i] > a:\n\t\t\toptions.append(1 + helper(i+1, True))\n\n\t\t# Choose the option that requires less total swaps\n\t\treturn min(options)\n\n\treturn min(helper(1, False), 1 + helper(1, True))\n```\n\n<br>\n\n**Top Down DP written more concicely: 108ms**\n```python\ndef minSwap(self, A: List[int], B: List[int]) -> int:\n\n\t@functools.lru_cache(None)\n\tdef helper(i, prev_swap):\n\t\tif i == len(A): return 0\n\t\ta,b = (B[i-1], A[i-1]) if prev_swap else (A[i-1], B[i-1])\n\t\treturn min(helper(i+1, False) if A[i] > a and B[i] > b else float(\'inf\'), 1 + helper(i+1, True) if A[i] > b and B[i] > a else float(\'inf\'))\n\treturn min(helper(1, False), 1 + helper(1, True)) if len(A) > 1 else 0\n```\n\n<br>\n\n**Bottom Up DP: 108 ms**\n```python\ndef minSwap(self, A: List[int], B: List[int]) -> int:\n\n\tn = len(A)\n\tdp = [[0 for _ in range(2)] for _ in range(n+1)]\n\tfor i in range(n-1, -1, -1):\n\t\tfor prev_swap in range(2):\n\t\t\ta,b = (B[i-1], A[i-1]) if prev_swap else (A[i-1], B[i-1])\n\t\t\tdp[i][prev_swap] = min(dp[i+1][0] if A[i] > a and B[i] > b else float(\'inf\'), 1 + dp[i+1][1] if A[i] > b and B[i] > a else float(\'inf\'))\n\n\treturn min(dp[1][0], 1 + dp[1][1]) if len(A) > 1 else 0\n```
[]