[C++] DP Top Down Vs. Bottom Up Solutions with 3 Base Cases, 105ms, 39.61MB
This is an interesting problem that, unlike its younger brother (solved here), gives us a lot of options at each turn, since we can:\n take the first 2 availabl
This is an interesting problem that, unlike [its younger brother](https://leetcode.com/problems/maximum-number-of-operations-with-the-same-score-i/) ([solved here](https://leetcode.com/problems/maximum-number-of-operations-with-the-same-score-i/solutions/4748186/c-check-pair-by-pair-0ms-19-97mb/)), gives us a lot of options at each turn, since we can:\n* take the first 2 available values;\n* take the last 2 available values;\n* take the first and last available values.\n\nAnd this also complicates our starting options, since potentially we would have to go through different paths, depending on what initial value we pick.\n\nWhen we have this kind of branching logic tree with multiple options at each step that we might end up recomputing again, the best way to go it is usually to store intermediate results as we go.\n\nIn other words, we will go DP ("Dynamic Programming") all the way on this one, starting from declaring at instance level:\n* `memo` is going to be our store for precomputed values;\n* `target` will represent our current target value for all possible sums;\n* `nums` will store the input vector.\n\nIn our main function, we will indees start assigning a value to `nums`, then declare a couple of local support variables:\n* `res` will store our best score, initially set to be `0` (`1` will work too, since we will always get at least a pair, the starting one, but I preferred to have that also for ease of debugging);\n* `len` will store the length of `nums`.\n\nWe will then deal with an edge case - `nums` is made of all identical values, in which case will just `return` half the value of `len` - which is what we will get as a maximum and minimum path in this occurrence, no matter what choices we make.\n\nIt might seem trivial, but I tested and this line alone cuts my running time short by ~200ms; and, yes; I knew LC was going to throw this kind of test at us with a very long vector.\n\nNext we will check for each of the three possible scenarios we mentioned initially what is the longest possible path, by:\n* filling `memo` with the sentinel value of `-1` to mark unexplored options;\n* computing the current `target` depending from the scenario;\n* update `res` to be the maximum between its current value and `1` plus the result of calling `dfs` with the indexes of the first available values in that scenario.\n\nThe `dfs` helper function will take the indexes of the first (`st`) and last (`ed`) available index and:\n* handle the base case of when we no longer have two numbers left to match within range (ie: `st >= ed`), in which case we will `return` `0`;\n* handle the base case of when we already computed this combination (ie: `memo[st][ed] != -1`), in which case we will `return` it;\n* handle the general case in which we will:\n    * declare the support variable `subRes` with initial value of `0`;\n    * test \n\nOnce done, back in our main function, we can just `return` `res` :)\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n- Space complexity:. $$O(n^2)$$\n\n# Code\n```cpp\nclass Solution {\n    int memo[2000][2000], target;\n    vector<int> nums;\n    int dfs(int st, int ed) {\n        // base case: done parsing!\n        if (st >= ed) return 0;\n        // base case: been here before!\n        if (memo[st][ed] != -1) return memo[st][ed];\n        // general case:\n        // support variables\n        int subRes = 0;\n        // 1st case: first two\n        if (nums[st] + nums[st + 1] == target) subRes = max(subRes, 1 + dfs(st + 2, ed));\n        // 2nd case: last two\n        if (nums[ed - 1] + nums[ed] == target) subRes = max(subRes, 1 + dfs(st, ed - 2));\n        // 3rd case: first and last\n        if (nums[st] + nums[ed] == target) subRes = max(subRes, 1 + dfs(st + 1, ed - 1));\n        return memo[st][ed] = subRes;\n    }\npublic:\n    int maxOperations(vector<int> &tmp) {\n        // populating instance variables\n        swap(tmp, nums);\n        // support variables\n        int res = 0, len = nums.size();\n        // edge case: all values are the same\n        if (equal(begin(nums) + 1, end(nums), begin(nums))) return len >> 1;\n        // 1st case: first two\n        memset(memo, -1, sizeof(memo));\n        target = nums[0] + nums[1];\n        res = max(res, 1 + dfs(2, len - 1));\n        // 2nd case: last two\n        memset(memo, -1, sizeof(memo));\n        target = nums[len - 2] + nums[len - 1];\n        res = max(res, 1 + dfs(0, len - 3));\n        // 3rd case: first and last\n        memset(memo, -1, sizeof(memo));\n        target = nums[0] + nums[len - 1];\n        res = max(res, 1 + dfs(1, len - 2));\n        return res;\n    }\n};\n```\nSame logic, marginally DRYer code in the main function and doing `memset` to restore `memo` only as needed, going almost 4X faster!\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n- Space complexity:. $$O(n^2)$$\n\n# Code\n```cpp\nclass Solution {\n    int memo[2000][2000], target;\n    vector<int> nums;\n    int dfs(int st, int ed) {\n        // base case: done parsing!\n        if (st >= ed) return 0;\n        // base case: been here before!\n        if (memo[st][ed] != -1) return memo[st][ed];\n        // general case:\n        // support variables\n        int subRes = 0;\n        // 1st case: first two\n        if (nums[st] + nums[st + 1] == target) subRes = max(subRes, 1 + dfs(st + 2, ed));\n        // 2nd case: last two\n        if (nums[ed - 1] + nums[ed] == target) subRes = max(subRes, 1 + dfs(st, ed - 2));\n        // 3rd case: first and last\n        if (nums[st] + nums[ed] == target) subRes = max(subRes, 1 + dfs(st + 1, ed - 1));\n        return memo[st][ed] = subRes;\n    }\npublic:\n    int maxOperations(vector<int> &tmp) {\n        // populating instance variables\n        swap(tmp, nums);\n        // support variables\n        int res = 0, len = nums.size();\n        array<int, 4> inputs[3];\n        if (equal(begin(nums) + 1, end(nums), begin(nums))) return len >> 1;\n        // creating the info for the three test cases\n        inputs[0] = {0, 1, 2, len - 1};\n        inputs[1] = {len - 2, len - 1, 0, len - 3};\n        inputs[2] = {0, len - 1, 1, len - 2};\n        // testing each different value of target\n        for (int i = 0; i < 3; i++) {\n            auto [firstIdx, secondIdx, st, ed] = inputs[i];\n            target = nums[firstIdx] + nums[secondIdx];\n            for (int j = 0, amt = len * sizeof(int); j < len; j++) memset(memo[j], -1, amt);\n            res = max(res, 1 + dfs(st, ed));\n        }\n        return res;\n    }\n};\n```\nMore or less same logic, with tabulation:\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n- Space complexity:. $$O(n^2)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int maxOperations(vector<int> &nums) {\n        // support variables\n        int res = 0, len = nums.size(), memo[len + 1][len + 1],\n            amt = (len + 1) * (len + 1) * sizeof(int);\n        array<int, 4> inputs[3] = {\n            {0, 1, 2, len - 1},\n            {len - 2, len - 1, 0, len - 3},\n            {0, len - 1, 1, len - 2}\n        };\n        if (equal(begin(nums) + 1, end(nums), begin(nums))) return len >> 1;\n        // testing each different value of target\n        for (int i = 0, subRes, target; i < 3; i++) {\n            auto [firstIdx, secondIdx, st, ed] = inputs[i];\n            target = nums[firstIdx] + nums[secondIdx];\n            memset(memo, 0, amt);\n            for (int j = 2; j <= len; j++) {\n                for (int st = 0, ed = j - 1; ed < len; st++, ed++) {\n                    if (nums[st] + nums[st + 1] == target)\n                        memo[j][st] = max(memo[j][st], 1 + memo[j - 2][st + 2]);\n                    if (nums[st] + nums[ed] == target)\n                        memo[j][st] = max(memo[j][st], 1 + memo[j - 2][st + 1]);\n                    if (nums[ed - 1] + nums[ed] == target)\n                        memo[j][st] = max(memo[j][st], 1 + memo[j - 2][st]);\n                }\n            }\n            res = max(res, memo[len][0]);\n        }\n        return res;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']