A 3D DP Problem

Jimmy (xiaoke) Shen
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.

--

--

No responses yet