本文主要是介绍【教3妹学编程-算法题】相同分数的最大操作数目 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3妹：2哥，干嘛呢，怎么又在吃泡面
2哥 : 这不是过年下血本，给小侄子买了一个ps5吗， 哎，我自己都舍不得用，不能让人说咱小气不是。
3妹：神马，他才6岁吧， 就这么喜欢玩游戏啦？
2哥 : 是啊， 没办法，之前许诺只要他考试好就给他买的
3妹：他考了多少分呀
2哥：100分，不过他们班相同分数的有十几个呢
3妹：哈哈哈哈，他们幼儿园题目是不是忒简单了啊
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 次操作。
提示：
2 <= nums.length <= 2000
1 <= nums[i] <= 1000
思路：
动态规划，
- 递归实现动态规划，每次尝试一种操作。
- 优先从缓存查找，避免重复计算。
- 中间结果缓存，使用二维数组，替代哈希集合（会超时），提高查询速度。
- 头和尾分数相等时，删除头和尾等效，只需二选一操作。
java代码：
class Solution {public int maxOperations(int[] nums) {int len = nums.length;// 枚举三种操作：删除头二、删除尾二、头尾各选一删除int score = nums[0] + nums[1];int maxOpt = 1 + maxOperations(nums, score, 2, len - 1, initCacheResult(len));if (nums[len - 2] + nums[len - 1] != score) {// 头和尾分数相等时，删除头和尾等效，只需二选一操作maxOpt = Math.max(maxOpt, 1 + maxOperations(nums, nums[len - 2] + nums[len - 1], 0, len - 3, initCacheResult(len)));}maxOpt = Math.max(maxOpt, 1 + maxOperations(nums, nums[0] + nums[len - 1], 1, len - 2, initCacheResult(len)));return maxOpt;}// 递归实现动态规划。优先从缓存查找，避免重复计算private int maxOperations(int[] nums, int score, int start, int end, int[][] cacheResultArray) {int maxOpt = 0;if (start >= end) {return maxOpt;}// 中间结果缓存，使用二维数组，替代哈希集合（会超时），提高查询速度// String resultKey = String.format("%s-%s", start, end);// Integer result = cacheResultMap.get(resultKey);// if (result != null) {// return result;// }Integer result = cacheResultArray[start][end];if (result != -1) {return result;}try {// 头和尾分数相等时，删除头和尾等效，只需二选一操作if (score == nums[start] + nums[start + 1]) {maxOpt = Math.max(maxOpt, 1 + maxOperations(nums, score, start + 2, end, cacheResultArray));if (end - start == 1) {return maxOpt;}} else if (score == nums[end] + nums[end - 1]) {maxOpt = Math.max(maxOpt, 1 + maxOperations(nums, score, start, end - 2, cacheResultArray));}if (score == nums[start] + nums[end]) {maxOpt = Math.max(maxOpt, 1 + maxOperations(nums, score, start + 1, end - 1, cacheResultArray));}return maxOpt;} finally {// 缓存中间结果// cacheResultMap.put(resultKey, maxOpt);cacheResultArray[start][end] = maxOpt;}}// 中间结果缓存，初始化private int[][] initCacheResult(int cap) {int[][] cacheResultArray = new int[cap][cap];for (int[] a : cacheResultArray) {Arrays.fill(a, -1);}return cacheResultArray;}
}
这篇关于【教3妹学编程-算法题】相同分数的最大操作数目 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
