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);
}
};
参考
