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

发表于 分类于 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

  • 区间DP

思路

一、问题重述（抽象化）

给定一个整数数组 \[ \text{nums} = [a_1, a_2, \dots, a_n] \] 每次操作可以 删除数组中相邻或两端的一对元素，具体有三种形式：

  1. 删除前两个元素 \[ (a_i, a_{i+1}) \]

  2. 删除后两个元素 \[ (a_{j-1}, a_j) \]

  3. 删除首尾两个元素 \[ (a_i, a_j) \]

但有一个全局约束：

所有操作中，被删除的一对元素之和 必须相同。

目标是： 在满足该约束的前提下，最大化操作次数。

二、关键观察（问题建模的核心）

1️⃣ 第一次操作决定“全局分数”

设每次操作的分数为： \[ s = x + y \] 由于所有操作分数必须一致，因此：

  • 第一次操作的分数 \(s\) 唯一决定了后续所有操作
  • 而第一次操作 只有三种可能：

\[ \begin{aligned} s_1 &= a_1 + a_2 \\ s_2 &= a_1 + a_n \\ s_3 &= a_{n-1} + a_n \end{aligned} \]

因此，只需枚举这三个候选分数，分别计算在该分数约束下最多能做多少步，取最大值即可。

三、状态设计（区间建模）

无论使用 区间 DP 还是 记忆化搜索，核心状态均为：

当前剩余子数组为区间 \([i, j]\)，在目标分数 \(s\) 下，最多能做多少次操作。

状态定义（数学形式）

固定分数 \(s\)

\[ f(i, j) = \text{区间 } [i, j] \text{ 内，所有操作和为 } s \text{ 的最大操作次数} \]

边界条件： \[ i \ge j \quad \Rightarrow \quad f(i, j) = 0 \] （区间内不足两个元素，无法继续操作）

四、状态转移方程（核心）

在区间 \([i, j]\) 内，若某种删除方式满足和为 \(s\)，即可进行一次操作，并转移到更小区间。

1️⃣ 删除首尾

若： \[ a_i + a_j = s \] 则： \[ f(i, j) = \max\left(f(i, j),\ 1 + f(i+1, j-1)\right) \]

2️⃣ 删除前两个

若： \[ a_i + a_{i+1} = s \] 则： \[ f(i, j) = \max\left(f(i, j),\ 1 + f(i+2, j)\right) \]

3️⃣ 删除后两个

若： \[ a_{j-1} + a_j = s \] 则： \[ f(i, j) = \max\left(f(i, j),\ 1 + f(i, j-2)\right) \]

总结（统一转移）

\[ f(i, j) = \max \begin{cases} 1 + f(i+1, j-1), & a_i + a_j = s \\ 1 + f(i+2, j), & a_i + a_{i+1} = s \\ 1 + f(i, j-2), & a_{j-1} + a_j = s \end{cases} \]

五、两种实现方式

实现一：区间 DP（三维，枚举分数）

思路

  • 用三维 DP 数组： \[ f[i][j][k] \]

    • \(i, j\)：区间端点（1-based）
    • \(k \in \{0,1,2\}\)：对应三种候选分数

  • 按区间长度从小到大枚举

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int k0, k1, k2;

    // 将实际的分数映射到 0 / 1 / 2
    inline int valid(int x) {
        if (x == k0) return 0;
        if (x == k1) return 1;
        if (x == k2) return 2;
        return -1;
    }

    int maxOperations(vector<int>& nums) {
        int n = nums.size();

        // f[i][j][v]：
        // 区间 [i, j] 在第 v 种目标分数下的最大操作次数
        static int f[2005][2005][3] = {};

        // 三种候选分数
        k0 = nums[0] + nums[n - 1];
        k1 = nums[n - 1] + nums[n - 2];
        k2 = nums[0] + nums[1];

        // 区间长度为 2 的初始化
        for (int i = 1; i < n; ++i) {
            int v = valid(nums[i - 1] + nums[i]);
            if (v != -1)
                f[i][i + 1][v] = 1;
        }

        // 按区间长度递推
        for (int len = 3; len <= n; ++len) {
            for (int j = len; j <= n; ++j) {
                int i = j - len + 1;

                // 删首尾
                int v = valid(nums[i - 1] + nums[j - 1]);
                if (v != -1)
                    f[i][j][v] = max(f[i][j][v], f[i + 1][j - 1][v] + 1);

                // 删后两个
                v = valid(nums[j - 2] + nums[j - 1]);
                if (v != -1)
                    f[i][j][v] = max(f[i][j][v], f[i][j - 2][v] + 1);

                // 删前两个
                v = valid(nums[i - 1] + nums[i]);
                if (v != -1)
                    f[i][j][v] = max(f[i][j][v], f[i + 2][j][v] + 1);
            }
        }

        // 三种分数取最大
        return max(f[1][n][0], max(f[1][n][1], f[1][n][2]));
    }
};

实现二：记忆化搜索（二维 + 外层枚举分数）

思路

  • 每次固定一个分数 \(s\)

  • 使用 DFS + 记忆化： \[ dfs(i, j) = f(i, j) \]

  • 对每个候选分数单独跑一次 DFS

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<int> arr;
    int n;
    int f[2005][2005]; // 仅与区间有关，分数在外层固定

    // dfs(i, j, s)：区间 [i, j]，目标分数 s
    int dfs(int i, int j, int s) {
        if (i >= j)
            return 0; // 不足两个数，不能操作

        int& res = f[i][j];
        if (res != -1)
            return res;

        res = 0;

        // 删首尾
        if (arr[i - 1] + arr[j - 1] == s)
            res = max(res, dfs(i + 1, j - 1, s) + 1);

        // 删前两个
        if (i + 1 <= j && arr[i - 1] + arr[i] == s)
            res = max(res, dfs(i + 2, j, s) + 1);

        // 删后两个
        if (i <= j - 1 && arr[j - 2] + arr[j - 1] == s)
            res = max(res, dfs(i, j - 2, s) + 1);

        return res;
    }

    int maxOperations(vector<int>& nums) {
        arr = nums;
        n = nums.size();
        int ans = 0;

        // 三种候选分数
        int cand[3] = {
            arr[0] + arr[1],
            arr[0] + arr[n - 1],
            arr[n - 2] + arr[n - 1]
        };

        // 对每个分数独立跑一次 DFS
        for (int t = 0; t < 3; ++t) {
            memset(f, -1, sizeof(f));
            ans = max(ans, dfs(1, n, cand[t]));
        }

        return ans;
    }
};

六、总结

  • 核心建模点：第一次操作决定全局分数，只需枚举 3 种可能；
  • 核心状态：区间 \([i, j]\)；
  • 核心转移：三种删除方式，对应三种区间缩小；
  • 两种等价实现：
    • 区间 DP：结构清晰，适合自底向上；
    • 记忆化搜索：代码直观，贴近数学定义。

这道题的本质是：

“固定目标值下的区间最大删除次数问题”