本文涉及知识点

C++动态规划
C++记忆化搜索

LeetCode3040. 相同分数的最大操作数目 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

动态规划+记忆化搜索

动态规划的状态表示

dp[i][j][k] 记录最大操作次数。k为0,上一次操作是删除nums[i-2]和nums[i-1]；k为1，上一次操作是删除nums[j+1]和nums[j+2]；k为2；上一次操作是删除nums[i-1]和nums[j+1]。
空间复杂度：O(nn)

动态规划的转移方程

如果j-i+1 <2 返回0。
如果有记录，则返回记录。
iDel = 上次删除的两个数之和。
如果nums[i]+nums[i+1] = = iDel
MaxSelf(ret ,1 + Rec(i+2,j,0)
如果nums[j] + nums[j-1] = = iDel
MaxSelf(ret ,1 + Rec(i,j-2,1)
如果nums[i] + nums[j] = = iDel
MaxSelf(ret ,1 + Rec(i+1,j-1,2)
记录并返回 ret

动态规划的初始化

全为-1。

动态规划的初始调用

1 + max(Rec(i+2,j,0),Rec(i,j-2,1),Rec(i+1,j-1,2))

代码（超时)

class Solution {
		public:
			int maxOperations(vector<int>& nums) {
				const int N = nums.size();
				vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(3,-1)));
				function<int(int, int, int)> Rec = [&](int i, int j, int k) {
					if (j - i + 1 < 2) { return 0; }
					auto& ret = dp[i][j][k];
					if (-1 != ret) return ret;
					ret = 0;
					int iDel = 0;
					if (0 == k) {
						iDel = nums[i - 2] + nums[i - 1];
					}
					if (1 == k) {
						iDel = nums[j + 1] + nums[j + 2];
					}
					if (2 == k) {
						iDel = nums[i-1] + nums[j + 1];
					}
					if (nums[i] + nums[i + 1] == iDel) {
						ret = max(ret, 1+Rec(i + 2, j, 0));
					}
					if (nums[j] + nums[j-1] == iDel) {
						ret = max(ret, 1 + Rec(i , j-2, 1));
					}
					if (nums[i] + nums[j] == iDel) {
						ret = max(ret, 1 + Rec(i+1, j - 1, 2));
					}
					return ret;
				};
				int ans = max(Rec(2, N - 1, 0), Rec(0, N - 3, 1));
				ans = max(ans, Rec(1, N - 2, 2));
				return ans + 1;
			}
		};

优化

iDel只有三种值，分别处理。

代码

class Solution {
		public:
			int maxOperations(vector<int>& nums) {
				const int N = nums.size();
				vector<vector<int>> dp(N, vector<int>(N,-1));				
				auto Do = [&](int i, int j,int iDel) {
					function<int(int, int)> Rec = [&](int i, int j) {
						if (j - i + 1 < 2) { return 0; }
						auto& ret = dp[i][j];
						if (-1 != ret) return ret;
						ret = 0;
						if (nums[i] + nums[i + 1] == iDel) {
							ret = max(ret, 1 + Rec(i + 2, j));
						}
						if (nums[j] + nums[j - 1] == iDel) {
							ret = max(ret, 1 + Rec(i, j - 2));
						}
						if (nums[i] + nums[j] == iDel) {
							ret = max(ret, 1 + Rec(i + 1, j - 1));
						}
						return ret;
					};
					return Rec(i, j);
				};
				int ans = max(Do(2, N - 1, nums[0]+nums[1]), Do(0, N - 3, nums[N-1]+nums[N-2]));
				ans = max(ans, Do(1, N - 2, nums[0]+nums.back()));
				return ans + 1;
			}
		};

单元测试

vector<int> nums;
		TEST_METHOD(TestMethod1)
		{
			nums = { 3, 2};
			auto res = Solution().maxOperations(nums);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod2)
		{
			nums = { 1,1,1,1 };
			auto res = Solution().maxOperations(nums);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod11)
		{
			nums = { 3, 2, 1, 2, 3, 4 };
			auto res = Solution().maxOperations(nums);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 3,2,6,1,4 };
			auto res = Solution().maxOperations(nums);
			AssertEx(2, res);
		}	
		TEST_METHOD(TestMethod13)
		{
			nums = { 1,9,7,3,2,7,4,12,2,6 };
			auto res = Solution().maxOperations(nums);
			AssertEx(2, res);
		}