[Mdp] lc3290. 最高乘法得分(二维dp+状态定义+状态转移+LCS问题+好题+周赛415_2)

1. 题目来源

链接：3290. 最高乘法得分

类似：

• [Mdp] lc3259. 超级饮料的最大强化能量(dp+状态表示+状态转移+状态机dp+周赛411_2)

2. 题目解析

挺不错的题目，纠结了一会贪心解法，但是没有什么卵用，证明不出来，代码难写。还是老老实实回归到 dp 求解吧。纠结程度和 [Mdp] lc3259. 超级饮料的最大强化能量(dp+状态表示+状态转移+状态机dp+周赛411_2) 一模一样…

思路：

• 状态定义：f[i][j]：在 b 中前 i 个与 a 中前 j 个字符所满足要求的最大得分。
• 状态转移：采用 选、不选 的状态转移思路：
  • b[i] 不选：f[i][j] = f[i-1][j]
  • b[i] 选：f[i][j]=f[i-1][j-1] + a[i] * b[j]
• 状态初始化：
  • 空间开辟要注意：共有 n 个数，需要开 n+1 个空间，因为是选 0、选1、选…、选 n 个。
  • 一开始都初始化最小值。针对 a 中一个都不选的情况，得分均为 0，所以 f[i][0] = 0;

总结：

• 能不贪心，就别贪心。
• 此类二维 dp 可以参考下 LCS 问题，有类似的状态定义及转移。
• 对于空间开辟，此类选不选问题，需要额外开辟一个空间。
• 本题的要求：b 数组选取的四个数是有序的。实际上可以思考下，dp 方程的 状态计算、状态转移 是恰好满足这个要求的。对于 f[4][2] 来讲，它要么是从 f[3][2] 转移，要么是从 f[3][1] 转移。

本问题抽象一下就有：

• a 数组有 n1 个数，b 数组有 n2 个数，且 n1 <= n2。
• 要求从 b 数组随机选中 n1 个数，按下标排序后。与 a 数组中的对应位置元素进行 f 函数的运算。
• 求 f 函数的最值。
• 这里的 f 函数给即有 加、减、乘、除 等运算。

• 时间复杂度：$O(nm)$
• 空间复杂度：$O(nm)$

代码：

常规写法：

class Solution {
public:
    long long maxScore(vector<int>& a, vector<int>& b) {
        typedef long long LL;
        int n = b.size(), m = a.size();
        vector<vector<LL>> f(n + 1, vector<LL>(m + 1, -1e18));
        f[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= 4; j++) {
                f[i][j] = f[i - 1][j];
                if (j > 0) f[i][j] = max(f[i][j], f[i - 1][j - 1] + (LL)a[j - 1] * b[i - 1]);
            }
        return f[n][4];
    }
};

简洁写法：更容易理解。

class Solution {
public:
    long long maxScore(vector<int>& a, vector<int>& b) {
        typedef long long LL;
        int n = b.size(), m = a.size();
        vector<vector<LL>> f(n + 1, vector<LL>(m + 1, -1e18));

        for (int i = 0; i <= n; i ++ ) f[i][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= 4; j++) 
                f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] + (LL)a[j - 1] * b[i - 1]);

        return f[n][4];
    }
};