https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/ from Google

Thinking process:

So for multipliers we can only move from left to right. For nums, we always have two choices, left most or the right most, which results in an O(2^N) solution.

Check the constraint, the nums length is 10^5, so the above approach will be O(2^(10^5)), which is too slow.

However, if we look into the each choice, the answer is actually decided by the state {nums_left_index, nums_right_index, multipliers_left_index}, so the state is limited, we can think of it like a O(N^3) states and thus the time is bounded in O(N^3).

Check the constraint again, O(N^3) is still too slow as well. The lengh of multipliers is 1000, so we can at most afford an O(N^2) solution.

Observe the state again, actually we can derive the nums_right_index because the numbers we consume in nums is the same as the numbers we consume in multipliers, so the nums_right_index is equal multipliers_left_index - (lengh_of_nums - nums_left_index - 1). With this, our state becomes {nums_left_index, multipliers_left_index} and thus we can have an O(N^2) top dow solution.

Here is the code.

 1class Solution {
 2public:
 3    int N, M;
 4    vector<vector<int>> dp;
 5    int dfs(int n, int m, vector<int>& nums, vector<int>& muls) {
 6        if (m == M) return 0;
 7        if (dp[n][m] != INT_MIN) return dp[n][m];
 8        int ans = max(nums[n]*muls[m] + dfs(n+1, m+1, nums, muls), nums[N-(m-n)-1]*muls[m] + dfs(n, m+1, nums, muls));
 9        return dp[n][m] = ans;
10    }
11    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
12        N = nums.size();
13        M = multipliers.size();
14        dp.resize(M, vector<int>(M, INT_MIN));
15        return dfs(0, 0, nums, multipliers);
16    }
17};