3290. 最高乘法得分

给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。

你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。你的得分将是 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3] 的值。

返回你能够获得的 最大 得分。

提示：

  • $a.length == 4$
  • $4 <= b.length <= 10^5$
  • $-10^5 <= a[i], b[i] <= 10^5$

思路

用dp来做，从后往前选取a[i]、b[j]相乘，考虑2种状态：

选当前a[i]、b[j]相乘，继续考虑a[i-1]、b[j-1]

不选选当前a[i]、b[j]相乘，继续考虑a[i]、b[j-1]

状态转换：

dfs(i,j)=max(dfs(i-1,j-1)+a[i]*b[j],dfs(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

class Solution {
public:
    long long maxScore(vector<int>& a, vector<int>& b) {
        int n=b.size();
        vector<array<long long,4>>memo(n);
        for(auto&row:memo){
            ranges::fill(row,LLONG_MIN);
        }
        auto dfs=[&](auto&&dfs,int i,int j)->long long{
            if(j<0)return 0;
            if(i<0){
                return LLONG_MIN/2;

            }
            auto &res=memo[i][j];
            if(res==LLONG_MIN){
                res=max(dfs(dfs,i-1,j),dfs(dfs,i-1,j-1)+(long long)a[j]*b[i]);
            }
            return res;
        };
        return dfs(dfs,n-1,3);
    }
};

参考