【区间DP】力扣3040. 相同分数的最大操作数目 II

给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：

选择 nums 中最前面两个元素并且删除它们。
选择 nums 中最后两个元素并且删除它们。
选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。

在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。

请你返回按照上述要求 最多 可以进行的操作次数。

示例 1：
输入：nums = [3,2,1,2,3,4]
输出：3
解释：我们执行以下操作：

• 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
• 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
• 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
  由于 nums 为空，我们无法继续进行任何操作。

示例 2：
输入：nums = [3,2,6,1,4]
输出：2
解释：我们执行以下操作：

• 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
• 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
  至多进行 2 次操作。

提示：
2 <= nums.length <= 2000
1 <= nums[i] <= 1000

记忆化搜索

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size();
        int memo[n][n];
        auto helper = [&](int i, int j, int target) -> int{
            memset(memo, -1, sizeof(memo));
            function<int(int, int)> dfs = [&](int i, int j) -> int{
                if(i >= j){
                    return 0;
                }

                if(memo[i][j] != -1){
                    return memo[i][j];
                }

                int ans = 0;
                if(nums[i] + nums[i+1] == target){
                    ans = max(ans, 1 + dfs(i+2, j));
                }
                if(nums[j-1] + nums[j] == target){
                    ans = max(ans, 1 + dfs(i, j-2));
                }
                if(nums[i] + nums[j] == target){
                    ans = max(ans, 1 + dfs(i+1, j-1));
                }
                memo[i][j] = ans;
                return ans;
            };
            return dfs(i, j);
        };

        int res = 0;
        res = max(res, helper(0, n - 1, nums[0] + nums[n - 1]));
        res = max(res, helper(0, n - 1, nums[0] + nums[1]));
        res = max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1]));
        return res;
    }
};

我们观察题目可以发现，题目中最多有三种分数，他们取决于第一次操作采用哪一种方式。也就是说如果我们采用回溯的方式，那么我们可以根据第一次操作的方式来分别进行回溯，因为这样子就知道后面回溯的分数要等于多少。

我们定义dfs(i,j)表示下标i到j的nums的相同分数的最大操作数目是多少，也就是说当我们知道我们要使分数为target，那么假设有一种方式nums[i] + nums[i+1] == target，那么这种方式就是可行的，我们继续进行回溯ans = max(ans, 1 + dfs(i+2, j))。注：ans是当前dfs的最大操作数目。

我们回溯的界限是当i >= j当时候，返回0，因为已经无法进行任何操作。再加入记忆话搜索的memo就可以减少时间复杂度。