[每日一题] 3040.相同分数的最大操作数目II

2024 年 06 月 08 日

99 次浏览

3468字数

> https://leetcode.cn/problems/maximum-number-of-operations-with-the-same-score-ii/description/?envType=daily-question&envId=Invalid%20Date

可以从三种操作中选择一个，并且很明显满足最优子结构，所以可以使用 DP 求解。

- 选择最前面两个，则可以通过 `dp[left + 2][right]` 转移过来；
- 选择最后两个，则可以通过 `dp[left][right - 2]` 转移过来；
- 选择第一个和最后一个，则可以通过 `dp[left + 1][right - 1]` 转移过来。

每次判断一下两个数相加的分数是否相同，相同则进行转移。

```c++
class Solution {
public:
    int maxOperations(std::vector<int>& nums) {
        const int n = nums.size();
        int dp[n][n];
        
        auto helper = [&] (int begin, int end, int mark) {
            memset(dp, -1, sizeof(dp));
            std::function<int(int, int)> dfs = [&] (int left, int right) {
                if (left >= right)
                    return 0;
                
                if (dp[left][right] != -1) 
                    return dp[left][right];
                
                int ops = 0;

if (nums[left] + nums[left + 1] == mark)
                    ops = std::max(ops, 1 + dfs(left + 2, right));
                if (nums[left] + nums[right] == mark)
                    ops = std::max(ops, 1 + dfs(left + 1, right - 1));
                if (nums[right] + nums[right - 1] == mark) 
                    ops = std::max(ops, 1 + dfs(left, right - 2));
                
                dp[left][right] = ops;
                return ops;
            };

return dfs(begin, end);
        };

int res = 0;
        res = std::max(res, helper(0, n - 1, nums[0] + nums[1]));
        res = std::max(res, helper(0, n - 1, nums[0] + nums[n - 1]));
        res = std::max(res, helper(0, n - 1, nums[n - 1] + nums[n - 2]));

return res;
    }
};
```

- 时间复杂度：$O(n^2)$ ，其中 $n$ 为 `nums` 数组的长度。
- 空间复杂度：$O(n^2)$ 。

### 优化

答案最大为 $\lfloor \frac{n}{2} \rfloor$ ，因此如果递归中出现了 $left \geq right$ 的情况，则说明已经执行了 $\lfloor \frac{n}{2} \rfloor$ 次操作，不需要再计算了。

```c++
class Solution {
public:
    int maxOperations(std::vector<int>& nums) {
        const int n = nums.size();
        int dp[n][n];
        
        bool isFinish = false;
        auto helper = [&] (int begin, int end, int mark) {
            if (isFinish)
                return 0;
                
            memset(dp, -1, sizeof(dp));
            std::function<int(int, int)> dfs = [&] (int left, int right) {
                if (isFinish)
                    return 0;

if (left >= right) {
                    isFinish = true;
                    return 0;
                }
                
                if (dp[left][right] != -1) 
                    return dp[left][right];
                
                int ops = 0;

dp[left][right] = ops;
                return ops;
            };

return dfs(begin, end);
        };

int res = 0;
        res = std::max(res, helper(2, n - 1, nums[0] + nums[1]));
        res = std::max(res, helper(1, n - 2, nums[0] + nums[n - 1]));
        res = std::max(res, helper(0, n - 3, nums[n - 1] + nums[n - 2]));

return res + 1;
    }
};
```

最后修改：2024 年 06 月 08 日