[Python] Top-Down Recursion with Memoization
Intuition\nBasically, at each node, you have two choices: 1) to switch and 2) to NOT switch to the other array. I recorded the indices of each value in each arr
**Intuition**\nBasically, at each node, you have two choices: 1) to switch and 2) to NOT switch to the other array. I recorded the indices of each value in each array to make the switching easier. I also kept two booleans `at1` and `at2` to check which array I am in currently. When we reach the base case, we just return 0, but along the path, we accumulate the current value to the result, then return the maximum of the paths at the end. It is important to use your own memoization and NOT to use `lru_cache` for this one because I think `lru_cache` evicts so many entries and causes recursion stack overflow.\n\n**Edit**\nReduced two booleans (`at1` and `at2` to one `at1`)\nThanks to [@dao5](https://leetcode.com/dao5)\n\n**Time/Space Complexity**\nTime: `O(N * 2) = O(N)` where `N = max(len(nums1), len(nums2))` due to memoization.\nSpace: Same as the Time Complexity\n\n**Code**\n```\nclass Solution:\n    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n        pos1 = {num: i for i, num in enumerate(nums1)}\n        pos2 = {num: i for i, num in enumerate(nums2)}\n        memo = [[-1 for _ in range(2)] for _ in range(max(len(nums1), len(nums2)))]\n\t\t\n        def rec(curr_i, at1):\n            if (curr_i >= len(nums1) and at1) or (curr_i >= len(nums2) and not at1):\n                return 0\n            if memo[curr_i][at1] == -1:\n                no_change = change = 0\n                if at1:\n                    if nums1[curr_i] in pos2:\n                        change = nums1[curr_i] + rec(pos2[nums1[curr_i]] + 1, False)\n                else:\n                    if nums2[curr_i] in pos1:\n                        change = nums2[curr_i] + rec(pos1[nums2[curr_i]] + 1, True)\n                no_change = (nums1[curr_i] if at1 else nums2[curr_i]) + rec(curr_i + 1, at1)\n                memo[curr_i][at1] = max(no_change, change)\n            return memo[curr_i][at1]\n        \n        return max(rec(0, True), rec(0, False)) % (10**9 + 7)\n```\n\t\nAny feedback would be great! Thanks.\n
[]