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

问题描述#

给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。

初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：

选择数组 nums 开头处或者末尾处 的整数 x 。

你获得 multipliers[i] * x 分，并累加到你的分数中。

将 x 从数组 nums 中移除。

在执行 m 步操作后，返回最大分数。

示例 1：
输入：nums = [1,2,3], multipliers = [3,2,1]
输出：14
解释：一种最优解决方案如下：
- 选择末尾处的整数 3 ，[1,2,3] ，得 3 * 3 = 9 分，累加到分数中。
- 选择末尾处的整数 2 ，[1,2] ，得 2 * 2 = 4 分，累加到分数中。
- 选择末尾处的整数 1 ，[1] ，得 1 * 1 = 1 分，累加到分数中。
总分数为 9 + 4 + 1 = 14 。
示例 2：
输入：nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
输出：102
解释：一种最优解决方案如下：
- 选择开头处的整数 -5 ，[-5,-3,-3,-2,7,1] ，得 -5 * -10 = 50 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-3,-2,7,1] ，得 -3 * -5 = 15 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-2,7,1] ，得 -3 * 3 = -9 分，累加到分数中。
- 选择末尾处的整数 1 ，[-2,7,1] ，得 1 * 4 = 4 分，累加到分数中。
- 选择末尾处的整数 7 ，[-2,7] ，得 7 * 6 = 42 分，累加到分数中。
总分数为 50 + 15 - 9 + 4 + 42 = 102 。
提示：

n == nums.length

m == multipliers.length

1 <= m <= 10³

m <= n <= 10⁵

-1000 <= nums[i], multipliers[i] <= 1000

解题思路#

用 \(\texttt{dp}[i][j]\) 表示左边取了 \(i\) 个数，右边取了 \(j\) 个数能够达到的最大值，那么有：

\[ \begin{aligned} \texttt{l}&=\texttt{nums}[i-1]\times\texttt{multipliers}[i+j-1]+\texttt{dp}[i-1][j] \\ \texttt{r}&=\texttt{nums}[n-j]\times\texttt{multipliers}[i+j-1]+\texttt{dp}[i][j-1] \\ \texttt{dp}[i][j]&=\max(l,r) \end{aligned} \]

然后最大值为 \(\texttt{dp}[i][m-i]\)。

方法一：记忆化搜索#

Python

手动维护缓存数组

class Solution:
    def maximumScore(self, nums: List[int], muls: List[int]) -> int:
        n, m = len(nums), len(muls)
        M = m + 1
        INF = 2 * 10 ** 9
        cache = [INF] * M * M

        def dp(i: int, j: int) -> int:
            q = i * M + j
            if cache[q] != INF:
                return cache[q]

            k = i + j
            if k == m:
                cache[q] = 0
            else:
                cache[q] = max(nums[i] * muls[k] + dp(i + 1, j), nums[n - 1 - j] * muls[k] + dp(i, j + 1))

            return cache[q]

        return dp(0, 0)

使用 @cache / @lru_cache

调用 cache_clear() 的原因

class Solution:
    def maximumScore(self, nums: List[int], muls: List[int]) -> int:
        n, m = len(nums), len(muls)

        @cache
        def dp(i: int, j: int, k: int) -> int:
            if k == m:
                return 0
            return max(nums[i] * muls[k] + dp(i + 1, j, k + 1), nums[j] * muls[k] + dp(i, j - 1, k + 1))

        ans = dp(0, n - 1, 0)
        dp.cache_clear()
        return ans

C++

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& muls) {
        int n = nums.size(), m = muls.size(), M = m + 1;
        int INF = 2e9;
        vector<int> cache(M * M, INF);

        function<int(int, int)> dp = [&] (int i, int j) {
            int q = i * M + j;

            if (cache[q] != INF) {
                return cache[q];
            }

            int k = i + j;

            if (k == m) {
                cache[q] = 0;
            } else {
                cache[q] = max(nums[i] * muls[k] + dp(i + 1, j), nums[n - 1 - j] * muls[k] + dp(i, j + 1));
            }

            return cache[q];
        };

        return dp(0, 0);
    }
};

时间复杂度：\(\mathcal{O}(m^2)\)
空间复杂度：\(\mathcal{O}(m^2)\)

方法二：递推#