力扣每日一题 6/8

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

题目分析：

 这道题的话数据量并不是很大，O(n**2)的复杂度就能过，根据题意分析呢，这道题可以用记忆化搜索来解答。主要思路就是dfs，确定一个初始值target，然后去遍历每个可以走的位置，取最大值。当我看到这道题的时候，有个大致思路但是难于代码实现，还是练的题少，于是查看了力扣大佬灵茶山艾府的解题思路，不得不承认确实写的很好，大致思路如下：

        定义 dfs(i,j)表示下标在闭区间 [i,j] 内的连续子数组，最多可以执行多少次操作。

        枚举三种操作方式，分别从 dfs(i+2,j)+1,dfs(i,j−2)+1,dfs(i+1,j−1)+1转移过来（如果能操作），取最大值，即为 dfs(i,j)。如果三种操作方式都不行，那么dfs(i,j)=0。

        递归终点：如果 i≥j，此时至多剩下一个数，无法操作，返回 0。

        递归入口：根据三种初始操作，分别为 dfs(2,n−1),dfs(0,n−3),dfs(1,n−2)。三者取最大值再加一（加上第一次操作），即为答案。

代码实现：

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def dfs(i, j, target):
            if i >= j:
                return 0
            ans = 0
            if nums[i] + nums[i + 1] == target:
                ans = max(ans, 1 + dfs(i + 2, j, target))
            if nums[i] + nums[j] == target:
                ans = max(ans, 1 + dfs(i + 1, j - 1, target))
            if nums[j - 1] + nums[j] == target:
                ans = max(ans, 1 + dfs(i , j - 2, target))
            return ans
        res = 0
        res = max(res, dfs(0, n - 1, nums[0] + nums[1]))
        res = max(res, dfs(0, n - 1, nums[0] + nums[n - 1]))
        res = max(res, dfs(0, n - 1, nums[n - 2] + nums[n - 1]))
        return res

总结：

        这段代码是一个用于求解在给定整数数组中，存在多少对数字之和为目标值的问题。函数 maxOperations 接受一个整数数组 nums 作为输入，然后定义了一个内部函数 dfs 用于递归求解满足条件的数字对数目。

        在 dfs 函数中，通过递归地考虑每一个数字与其他数字的组合情况，并更新最优解。最后在 maxOperations 函数中，通过调用 dfs 函数并传入不同的数对目标值，来求解满足条件的数字对的最大数量。

        总体来说，这段代码使用动态规划的思想来解决问题，通过记忆化搜索避免重复计算。