leetcode 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.

Example 1:

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:

• Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
• Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
• Choose from the end, [1], adding 1 * 1 = 1 to the score.
  The total score is 9 + 4 + 1 = 14.
  Example 2:

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:

• Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
• Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
• Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
• Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
• Choose from the end, [-2,7], adding 7 * 6 = 42 to the score.
  The total score is 50 + 15 - 9 + 4 + 42 = 102.

nums中每次要么从头，要么从尾取出一个数字，
multipliers中的数字是按从左到右的顺序取，
这俩取出来的数字相乘，加起来，最后能得到的最大分数是多少。

思路：

是不是曾几何时想到了greedy?
每次取能使score=nums[left or right] * multipliers[i] 较大的?
这对example1是行得通的，但是对example2就行不通了（自行验证）。

那就只有笨办法，所有可能的列举一遍，取最大的score。
但是这种笨办法肯定会TLE的，因为有很多重复的计算，如下图的v(e)和v(a)。

这不难让人想到把重复计算的部分保存起来，直接取结果，
就是DP.

但是DP的状态怎么定义呢。
看score的计算：score=nums[left or right] * multipliers[i]
这里面需要知道left, right指针指向哪个数字，还要知道i, 也就是到目前为止操作了几次。
后面把这个i 称为 op (操作次数）

那岂不是要三维DP？
有没有注意到left + right = op的，操作次数就那么多，不是left 就是 right.
注意，这里的right是指在右边取了多少个数字，并不是指向nums的第几个元素，
但是现在想知道的right就是index, 这样才能通过nums[right]把数字取出来，
可通过op - left 知道右边已经取了几个数字，那下一个要取的右边数字的index就是 nums.length - 1 - (op - left)。
理解这点非常重要。

那么 dp[op][left] 定义为操作了op次，其中左边取了left个数字。

既然right可以通过left 和 op确定，那就只需要二维DP了。
如果取nums左边的数字，那么score1 = nums[left] * multipliers[op]
如果取nums右边的数字，那么score2 = nums[right] * multipliers[op]

但这只是当前这一步的score, 还要加上后续的计算，
经过这一步的计算，实际的操作数为op+1, 左边的数字个数为left+1
score1 = nums[left] * multipliers[op] + dp[op + 1][left + 1]
如果取右边的数字，那么left是不变的，op+1
score2 = nums[right] * multipliers[op] + dp[op+1][left]

还有一个问题，初始化。
你可能会想，op=0的dp为0，就是第一行为0.

但是看上面的图或state公式，可以看出，计算dp[op][left],
我们需要的是dp[op+1][left+1] 和 dp[op][left]
所以最终的初始化应该是dp[m]行=0，m=multipliers.length,

为什么呢？这样想，
在最开始的时候，score是不确定的，我不知道要选哪个数字，后面会选哪个数字，
只有在最后所有的数字选完以后，没有数字了，这时候的score肯定是0.
倒数第2步，在0的基础上加上剩下的最后一个数字，以此类推。
所以我们的计算是从最后往前计算的。

理解了这些以后，就好办了。

m为multipliers的长度，n为nums的长度。
所以声明DP数组，dp[m+1][n+1] ，
No，这样会MLE，内存超标。
这也是一个坑，
nums可以很长，但是很多数字用不到，因为要乘的数字在multipliers里，它就那么多，
left + right最多也不过m而已。所以要声明dp[m+1][m+1]

这个是按上面思路的做法，递归DP。

class Solution {
    Integer[][] dp;
    int n = 0;
    int m = 0;
    public int maximumScore(int[] nums, int[] multipliers) {
        n = nums.length;
        m = multipliers.length;
        
        dp = new Integer[m+1][m+1];
        
        return getScore(nums, multipliers, 0, 0);
    }
    
    int getScore(int[] nums, int[] multi, int op, int left) {
        if(op == m) return 0;
        if(dp[op][left] != null) return dp[op][left];
        
        int num1 = nums[left] * multi[op] + getScore(nums, multi, op+1, left+1);
        int num2 = nums[n-1-(op-left)] * multi[op] + 
            getScore(nums, multi, op+1, left);
        
        return dp[op][left] = Math.max(num1, num2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面做法能通过，但比较慢，
改进一下，不要递归了。
left从右到左，从左到右都可以。

public int maximumScore(int[] nums, int[] multipliers) {
    int n = nums.length;
    int m = multipliers.length;
    
    int[][] dp = new int[m+1][m+1];
    
    for(int op = m-1; op >= 0; op--) {
        for(int left = op; left >= 0; left--) {
        //也可以是for(int left = 0; left <= op; left++) {
            int score1 = nums[left] * multipliers[op] + dp[op+1][left+1];
            int score2 = nums[n-1-(op-left)] * multipliers[op] +
                dp[op+1][left];
            dp[op][left] = Math.max(score1, score2);
        }
    }
    return dp[0][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上面是标准的二维DP，
有没有办法只用一维数组节省空间和时间呢？

注意到op只和上一个op相关，
left一定要从左到右覆盖上一层数据，因为用到了left+1

public int maximumScore(int[] nums, int[] multipliers) {
    int n = nums.length;
    int m = multipliers.length;
    
    int[][] dp = new int[m+1][m+1];
    
    for(int op = m-1; op >= 0; op--) {
        for(int left = 0; left <= op; left++) {
            int score1 = nums[left] * multipliers[op] + dp[op+1][left+1];
            int score2 = nums[n-1-(op-left)] * multipliers[op] +
                dp[op+1][left];
            dp[op][left] = Math.max(score1, score2);
        }
    }
    return dp[0][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16