A 3D DP Problem
1 min readFeb 21, 2021
Problem
This is the 3rd problem of weekly leetcode contest of Feb 20, 2021.
1770. Maximum Score from Performing Multiplication Operations
Explanation
Using 3 variables to represent the DP state:
- l, r, turn where l is the next available left index and r is the next available right index and turn is picking from left or picking from right.
As the nums has a large size, we can use the index of multipliers instead. And the r can be inffered from the multipliers’ index.
So fincally, we use
- (i, j, turn) where i is the next available left index.
- j is the multipliers index, r can be inferred from i and j.
- turn == 1: pick from left
- turn == 0: pick from right.
Code
const int LEFT = 1, RIGHT = 0;
int dp[1001][1001][2];
class Solution {
public:
vector<int>nums, multipliers;
int helper(int i, int j, int turn){
if (dp[i][j][turn]!=0x3f3f3f3f) return dp[i][j][turn];
int l = i, r = nums.size() - (j + 1 - i);
if (j == multipliers.size()) return 0;
int ret = 0;
if (turn == LEFT)
ret = nums[l]*multipliers[j] + max(
helper(i+1, j+1, LEFT), helper(i+1, j+1, RIGHT));
else
ret = nums[r]*multipliers[j] + max(
helper(i, j+1, LEFT), helper(i, j+1, RIGHT));
return dp[i][j][turn] = ret;
}
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
this -> nums = nums; this -> multipliers = multipliers;
memset(dp, 0x3f, sizeof dp);
return max(helper(0, 0, LEFT), helper(0, 0, RIGHT));
}
};
Thanks for reading.