Simple Dp Memoization - explained
Intuition\nThe main challenge of this problem is to find the maximum number of operations that can be performed on the array nums such that every operation yiel
# Intuition\nThe main challenge of this problem is to find the maximum number of operations that can be performed on the array `nums` such that every operation yields the same score (the sum of the two deleted elements). The allowed operations involve removing either the first two elements, the last two elements, or the first and last element of the array. \n\nMy initial thought was to use a recursive approach that explores all possible deletion sequences and leverages memoization to avoid recomputing overlapping subproblems. The goal is to maximize the number of deletions while ensuring the sum remains consistent across all operations.\n\n# Approach\n1. **Recursive Depth-First Search (DFS) with Memoization**:\n   - We define a recursive function `dfs(start, stop, score)` that explores different deletion combinations:\n     - `start` and `stop` denote the current boundaries of the array.\n     - `score` is the sum we aim to maintain for every operation.\n   - The base case occurs when there are fewer than 2 elements between `start` and `stop`, which means no more operations can be performed.\n   - For each call, we have three choices:\n     1. Remove the first and last elements if their sum matches `score`.\n     2. Remove the first two elements if their sum matches `score`.\n     3. Remove the last two elements if their sum matches `score`.\n   - We use a cache (a dictionary) to memoize results for specific `(start, stop, score)` tuples to optimize performance and avoid recomputation.\n   - Finally, we initiate the search with three potential scores:\n     1. The sum of the first two elements.\n     2. The sum of the last two elements.\n     3. The sum of the first and last element.\n   - The result is the maximum number of operations found among the three initial calls.\n\n# Complexity\n- **Time Complexity**: \n  - The worst-case time complexity is approximately $$O(n^3)$$ because for each combination of `start`, `stop`, and `score`, we are performing recursive calls and storing results in the cache. The memoization helps to prevent redundant calculations.\n  \n- **Space Complexity**: \n  - $$O(n^2)$$ due to the cache used to store results for different `(start, stop, score)` combinations, and the recursion stack can go up to a depth of $$O(n)$$ in the worst case.\n\n# Code\n```python []\nclass Solution(object):\n    def maxOperations(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        cache = {}\n        n = len(nums)\n        def dfs(start, stop, score):\n            if stop - start < 2:\n                return 0\n            if (start, stop, score) in cache:\n                return cache[(start, stop, score)]\n            r1, r2, r3 = 0, 0, 0\n            if nums[start] + nums[stop-1] == score:\n                r1 = 1 + dfs(start+1, stop-1, score)\n            if nums[start] + nums[start+1] == score:\n                r2 = 1 + dfs(start+2, stop, score)\n            if nums[stop-2] + nums[stop-1] == score:\n                r3 = 1 + dfs(start, stop-2, score)\n            cache[(start, stop, score)] = max(r1, r2, r3)\n            return max(r1, r2, r3)\n        return max(\n                dfs(0, n, nums[0]+nums[1]), \n                dfs(0, n, nums[0]+nums[-1]), \n                dfs(0, n, nums[-2]+nums[-1])\n            )\n\n\n```
['Python']