力扣：3040. 相同分数的最大操作数目 II（Java,动态规划）

目录

• 题目描述：
• 示例 1：
• 示例 2：
• 代码实现：

题目描述：

给你一个整数数组 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 次操作。

代码实现：

class Solution {
public int maxOperations(int[] nums) {
int n = nums.length;// 数组长度
int res = 0;// 最终结果
int[][] memo = new int[n][n];// 构造记忆数组：记录每一个状态存在的最大操作数
// 将记忆数组中的所有元素初始化为-1
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);// 使用数组填充函数
}
// 枚举每一种初始状态后，开始递归搜索
// 1.删除首尾元素
res = Math.max(res, helper(memo, nums, 0, n - 1, nums[0] + nums[n - 1]));
// 2.删除前两个元素
res = Math.max(res, helper(memo, nums, 0, n - 1, nums[0] + nums[1]));
// 3.删除后两个元素
res = Math.max(res, helper(memo, nums, 0, n - 1, nums[n - 1] + nums[n - 2]));
return res;
}
// 返回nums数组在i到j区间内，保证target一致，存在的最大操作次数
int helper(int[][] memo, int[] nums, int i, int j, int target) {
if (i >= j) {// 不存在区间的情况
return 0;
}
if (memo[i][j] != -1 && i != 0) {// 如果当前位置已被记录，直接返回结果，减少遍历次数
// i不能为0，这样才能覆盖每一种情况
return memo[i][j];
}
int ans = 0;// 求本轮区间中的最大操作数目
// 1.删除前两个元素的情况
if (nums[i] + nums[i + 1] == target) {
// 取较大值：将i索引右移两位得到下一轮状态+1与 当前ans比较
ans = Math.max(ans, helper(memo, nums, i + 2, j, target) + 1);
}
// 2.删除首尾元素的情况
if (nums[i] + nums[j] == target) {
// 下一轮区间状态+1 与 上一轮最大操作数的 较大值
ans = Math.max(ans, helper(memo, nums, i + 1, j - 1, target) + 1);
}
// 3.删除后两个元素的情况
if (nums[j - 1] + nums[j] == target) {
// 下一轮区间状态+1 与 上一轮最大操作数的 较大值
ans = Math.max(ans, helper(memo, nums, i, j - 2, target) + 1);
}
memo[i][j] = ans;// 记录当前最大操作数到记忆数组
return ans;// 返回最后一次递归结果
}
}