1770. Maximum Score from Performing Multiplication Operations

Posted on

Description

Submission

class Solution {
public:
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int n = nums.size();
int m = multipliers.size();
vector<vector<int>> dp(m+1, vector<int>(m+1, INT_MIN/2));
nums.insert(nums.begin(), 0);
dp[0][0] = 0;
int ret = INT_MIN / 2;
for(int len = 1; len <= m; ++len) {
for(int i = 0; i <= len; ++i) {
int j = len - i;
if(i >= 1) dp[i][j] = max(dp[i][j], dp[i-1][j] + nums[i] * multipliers[len-1]);
if(j >= 1) dp[i][j] = max(dp[i][j], dp[i][j-1] + nums[n-j+1] * multipliers[len-1]);
if(len == m) ret = max(ret, dp[i][j]);
}
}
return ret;
}
};
// dp[i][j]: i-th on the left and j-th on the right(inclusive)
// 0 1 2
// 0 X X X X X X X
// i. j
// dp[i][j] = max(dp[i-1][j] + nums[i] * multipliers[i+j]
// dp[i][j-1] + nums[n-j+1] * multipier[i+j]
// )