1770. Maximum Score from Performing Multiplication Operations

You are given two integer arrays nums and multipliers of size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the ith operation (1-indexed), you will:

• Choose one integer x from either the start or the end of the array nums.
• Add multipliers[i] * x to your score.
• Remove x from the array nums.

Return the maximum score after performing m operations.

class Solution {
    int dfs(vector<int>& nums, vector<int>& mul, vector<vector<int>>& dp, vector<vector<bool>>& visit, int i, int j) {
        if(j >= mul.size())
            return 0;
        //j for mul
        //i for nums
        if(!visit[j][i]) {
            int k = nums.size() - 1 - (j - i); //gap
            dp[j][i] = max(nums[i] * mul[j] + dfs(nums, mul, dp, visit, i + 1, j + 1),
                    nums[k] * mul[j] + dfs(nums, mul, dp, visit, i, j + 1));
            
            visit[j][i] = true;
        }
        return dp[j][i];
    }
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        vector<vector<int>> dp(multipliers.size() + 1, vector<int>(multipliers.size() + 1));
        vector<vector<bool>> visit(multipliers.size() + 1, vector<bool>(multipliers.size() + 1, false));
        return dfs(nums, multipliers, dp, visit, 0, 0);
    }
};