1770. 执行乘法运算的最大分数

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

考点

  • 区间DP

思路

一、问题抽象与整体建模

给定两个数组：

  • 原数组 \[ \text{nums} = [a_0, a_1, \dots, a_{n-1}] \]

  • 乘子数组 \[ \text{multipliers} = [b_0, b_1, \dots, b_{m-1}] \]

需要进行 恰好 \(m\) 次操作。 第 \(k\) 次操作（从 0 开始）必须：

  • 从 nums 当前剩余数组的 左端或右端 取一个数；

  • 获得分数： \[ a \times b_k \]

目标是 最大化总得分。

二、核心建模思想：用“删掉的个数”而不是“剩余区间”

1. 为什么不直接做三维区间 DP？

直观想法是： \[ f(k, l, r) = \text{第 } k \text{ 次操作时，当前区间为 } [l,r] \text{ 的最大得分} \] 但存在一个关键事实：

  • 每做一次操作，区间长度减少 1；
  • 初始区间长度为 \(n\)；
  • 做了 \(k\) 次操作后，剩余区间长度恒为 \(n-k\)。

因此： \[ r - l + 1 = n - k \] 这说明三者 \(k,l,r\) 并不独立，三维 DP 中有一维是冗余的。

2. 等价但更优的状态描述

改用 “从左右删了多少个” 来描述状态。

定义：

\(f(i,j)\)： 已经从 左边删了 \(i\) 个、从 右边删了 \(j\) 个， 在当前状态下，继续完成剩余操作所能获得的最大得分。

此时有：

  • 已执行操作数： \[ k = i + j \]

  • 当前使用的乘子： \[ b_k \]

  • 当前剩余区间为： \[ [\, i,\; n-1-j \,] \]

三、状态转移方程推导

在状态 \((i,j)\)（且 \(i+j < m\)）时，有两种选择：

1. 从左端取数

  • 取的数为：\(\text{nums}[i]\)
  • 得分：\(\text{nums}[i] \times b_{i+j}\)
  • 进入状态：\((i+1, j)\)

\[ f(i,j) \rightarrow b_{i+j}\cdot \text{nums}[i] + f(i+1,j) \]

2. 从右端取数

  • 取的数为：\(\text{nums}[n-1-j]\)
  • 得分：\(\text{nums}[n-1-j] \times b_{i+j}\)
  • 进入状态：\((i, j+1)\)

\[ f(i,j) \rightarrow b_{i+j}\cdot \text{nums}[n-1-j] + f(i,j+1) \]

3. 状态转移方程

\[ \boxed{ f(i,j) = \max\Big( b_{i+j}\cdot \text{nums}[i] + f(i+1,j),\; b_{i+j}\cdot \text{nums}[n-1-j] + f(i,j+1) \Big) } \]

4. 边界条件

当乘子用完，即： \[ i + j = m \] 后续无法继续操作，得分为 0： \[ f(i,j) = 0 \]

5. 状态规模

  • \(0 \le i \le m\)

  • \(0 \le j \le m\)

  • 且必须满足： \[ i + j \le m \]

状态数为： \[ \sum_{k=0}^{m} (k+1) = O(m^2) \]

四、实现一：记忆化搜索（Top-down DP）

设计思路

  • 直接按数学定义写递归；
  • 使用二维数组 f[i][j] 记忆化；
  • 递归深度最多为 \(m\)。

特点

  • 代码最贴近状态定义；
  • 逻辑清晰，便于验证正确性；
  • 有递归开销。

代码（带注释）

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
class Solution {
public:
    int n, m;
    int f[1005][1005];
    const int neg = 0xcfcfcfcf;

    // dfs(i, j): 左边删了 i 个，右边删了 j 个后的最大得分
    int dfs(int i, int j, vector<int>& nums, vector<int>& multipliers) {
        // 乘子已用完
        if (i + j >= m)
            return 0;

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

        // 选择左端
        res = dfs(i + 1, j, nums, multipliers)
              + nums[i] * multipliers[i + j];

        // 选择右端
        res = max(
            res,
            dfs(i, j + 1, nums, multipliers)
            + nums[n - 1 - j] * multipliers[i + j]
        );

        return res;
    }

    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        memset(f, 0xcf, sizeof(f));
        n = nums.size();
        m = multipliers.size();
        return dfs(0, 0, nums, multipliers);
    }
};

五、实现二：二维动态规划（Bottom-up）

设计思路

  • 将记忆化搜索改为递推；
  • 按 \(i+j\) 从大到小填表；
  • 确保转移所需的状态已计算完成。

遍历顺序

  • 外层：\(i\) 从 \(m-1\) 到 \(0\)
  • 内层：\(j\) 从 \(m-1-i\) 到 \(0\)

这样保证 (i+1, j) 和 (i, j+1) 已经被计算。

代码（带注释）

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
class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int f[1005][1005] = {};
        int n = nums.size();
        int m = multipliers.size();

        // i + j 从 m-1 递减到 0
        for (int i = m - 1; i >= 0; --i) {
            for (int j = m - 1 - i; j >= 0; --j) {
                // 左端选择
                int takeLeft =
                    f[i + 1][j] + nums[i] * multipliers[i + j];

                // 右端选择
                int takeRight =
                    f[i][j + 1] + nums[n - 1 - j] * multipliers[i + j];

                f[i][j] = max(takeLeft, takeRight);
            }
        }

        return f[0][0];
    }
};

六、实现三：滚动数组优化（空间压缩）

优化依据

状态转移： \[ f(i,j) \leftarrow f(i+1,j),\ f(i,j+1) \] 说明：

  • 当前行只依赖「下一行」和「当前行右侧」
  • 可以将二维数组压缩为一维数组 f[j]

设计要点

  • f[j] 表示当前 i 层的状态；
  • f[j] 在更新前是 f(i+1, j)；
  • f[j+1] 已是当前行的 f(i, j+1)；
  • 内层 j 必须 从大到小遍历。

代码（带注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int f[1005] = {};
        int n = nums.size();
        int m = multipliers.size();

        // i 从 m-1 到 0
        for (int i = m - 1; i >= 0; --i) {
            // j 从 m-1-i 到 0
            for (int j = m - 1 - i; j >= 0; --j) {
                int takeLeft =
                    f[j] + nums[i] * multipliers[i + j];
                int takeRight =
                    f[j + 1] + nums[n - 1 - j] * multipliers[i + j];
                f[j] = max(takeLeft, takeRight);
            }
        }

        return f[0];
    }
};

七、总结

  • 本题的关键并不在“区间 DP”，而在于：

    用「删掉的数量」隐式表示区间

  • 核心约束是： \[ \text{已删左} + \text{已删右} = \text{已使用乘子数} \]

  • 从而将表面三维问题压缩为二维；

  • 在此基础上：

    • 记忆化搜索：最直观；
    • 二维 DP：更高效、无递归；
    • 滚动数组：空间最优。