3040.相同分数的最大操作数目II

链接：3040.相同分数的最大操作数目II
难度：Medium
标签：记忆化搜索、数组、动态规划
简介：在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。请你返回按照上述要求 最多 可以进行的操作次数。

题解 1 - python

• 编辑时间：2024-06-08
• 执行用时：2313ms
• 内存消耗：377.62MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def dfs(l: int, r: int, score: int) -> int:
            if r - l + 1 < 2: return 0
            res = 0
            if nums[l] + nums[l + 1] == score:
                res = max(res, 1 + dfs(l + 2, r, score))
            if nums[r] + nums[r - 1] == score:
                res = max(res, 1 + dfs(l, r - 2, score))
            if nums[l] + nums[r] == score:
                res = max(res, 1 + dfs(l + 1, r - 1, score))
            return res
        return 1 + max(
            dfs(2, n - 1, nums[0] + nums[1]),
            dfs(0, n - 1 - 2, nums[n - 1] + nums[n - 2]),
            dfs(1, n - 1 - 1, nums[0] + nums[n - 1])
        )