Every day a Leetcode

题目来源：3040. 相同分数的最大操作数目 II

解法1：记忆化搜索

第一步可以做什么？做完后，剩下要解决的问题是什么？

• 删除前两个数，剩下 nums[2] 到 nums[n−1]，这是一个连续的子数组。
• 删除后两个数，剩下 nums[0] 到 nums[n−3]，这也是一个连续的子数组。
• 删除第一个和最后一个数，剩下 nums[1] 到 nums[n−2]，这还是一个连续的子数组。

无论怎么删除，剩下的都是连续子数组，都是和原问题相似的，规模更小的子问题。我们可以用子数组的左右端点下标表示状态，状态的值就是这个子数组的操作次数。

如果确定了第一次删除的元素和，那么后续删除的元素和也就确定了（因为每次操作的元素和必须相等）。三种操作，对应着至多三种不同的元素和，分别用三次区间 DP 解决。

代码：

#
# @lc app=leetcode.cn id=3040 lang=python3
#
# [3040] 相同分数的最大操作数目 II
## @lc code=start
class Solution:def maxOperations(self, nums: List[int]) -> int:@cachedef dfs(i: int, j: int, target: int) -> int:if i >= j:return 0res = 0# 删除前两个数if nums[i] + nums[i + 1] == target:res = max(res, dfs(i + 2, j, target) + 1)# 删除后两个数if nums[j - 1] + nums[j] == target: res = max(res, dfs(i, j - 2, target) + 1)# 删除第一个和最后一个数if nums[i] + nums[j] == target:res = max(res, dfs(i + 1, j - 1, target) + 1)return resn = len(nums)res1 = dfs(2, n - 1, nums[0] + nums[1])  # 删除前两个数res2 = dfs(0, n - 3, nums[-2] + nums[-1])  # 删除后两个数res3 = dfs(1, n - 2, nums[0] + nums[-1])  # 删除第一个和最后一个数return max(res1, res2, res3) + 1  # 加上第一次操作# @lc code=end

结果：

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组 nums 的长度。

空间复杂度：O(n²)，其中 n 是数组 nums 的长度。

解法2：动态规划

代码：

/** @lc app=leetcode.cn id=3040 lang=cpp** [3040] 相同分数的最大操作数目 II*/// @lc code=start// 区间 DP + 记忆化搜索class Solution
{
public:int maxOperations(vector<int> &nums){if (nums.size() < 2)return 0;int n = nums.size();int memo[n][n];function<int(int, int, int)> 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;int &res = memo[i][j]; // 注意这里是引用if (res != -1)return res;res = 0;// 删除前两个数if (nums[i] + nums[i + 1] == target)res = max(res, dfs(i + 2, j) + 1);// 删除后两个数if (nums[j - 1] + nums[j] == target)res = max(res, dfs(i, j - 2) + 1);// 删除第一个和最后一个数if (nums[i] + nums[j] == target)res = max(res, dfs(i + 1, j - 1) + 1);return res;};return dfs(i, j);};// 删除前两个数int res1 = helper(2, n - 1, nums[0] + nums[1]);// 删除后两个数int res2 = helper(0, n - 3, nums[n - 2] + nums[n - 1]);// 删除第一个和最后一个数int res3 = helper(1, n - 2, nums[0] + nums[n - 1]);int ans = max({res1, res2, res3}) + 1; // 加上第一次操作return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组 nums 的长度。

空间复杂度：O(n²)，其中 n 是数组 nums 的长度。