f[i][j] 表示 nums 从 i 开始，multiplier 从 j 开始的所有可能方案的最大分数
，nums 末尾已经被使用的数的个数一定是 (j-i)，因此最后一个数的下标为 n - (j - i) - 1。

f[i][j] 每次针对 multiplier[j] 有两种转移方案：

• 选开头的 nums[i] 来乘，剩下的方案表示为 f[i+1][j+1]
• 选结尾的 nums[n - (j - i) - 1] 来乘，剩下的方案表示为 f[i][j+1]

注意到从前面数和从后面数，下标大于 2*10^3 的 nums[i] 一定不会被访问，因此数组 f 只用开到 m*m 维即可（开成 n*m 会 TLE）

最后结果就是 f[0][0]

const int M = 1e3 + 10;
int f[M][M];

class Solution {
    int n, m;

   public:
    int maximumScore(vector<int>& nums, vector<int>& mul) {
        n = nums.size(), m = mul.size();
        memset(f, 0, sizeof f);
        for (int j = m - 1; j >= 0; j--) {
            for (int i = 0; i <= j; i++) {
                f[i][j] = max(
                    f[i + 1][j + 1] + nums[i] * mul[j],
                    f[i][j + 1] + (nums[n - (j - i) - 1]) * mul[j]);
            }
        }
        return f[0][0];
    }
};

记忆化搜索版本：

#include <bits/stdc++.h>
using namespace std;
const int M = 1e3 + 10;
int f[M][M];
class Solution {
    int n, m;
    int dp(int i, int j, vector<int>& nums, vector<int>& mul) {
        if (j >= m) return 0;
        if (f[i][j] != 0x3f3f3f3f) return f[i][j];
        f[i][j] = max(
            dp(i + 1, j + 1, nums, mul) + nums[i] * mul[j],
            dp(i, j + 1, nums, mul) + (nums[n - (j - i) - 1]) * mul[j]);
        return f[i][j];
    }

   public:
    int maximumScore(vector<int>& nums, vector<int>& mul) {
        memset(f, 0x3f, sizeof f);
        n = nums.size(), m = mul.size();
        return dp(0, 0, nums, mul);
    }
};