「这是我参与11月更文挑战的第9天，活动详情查看： 2021最后一次更文挑战 」

1770.执行乘法运算的最大分数

给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ****，其中 n >= m ，数组下标 从 1 开始 计数。

初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（ 从 1 开始 计数）中，需要：

在执行 ** m 步操作后，返回 最大 分数 。

示例 1：

输入： nums = [1,2,3], multipliers = [3,2,1]
输出： 14
解释： 一种最优解决方案如下：
- 选择末尾处的整数 3 ，[1,2,3] ，得 3 * 3 = 9 分，累加到分数中。
- 选择末尾处的整数 2 ，[1,2] ，得 2 * 2 = 4 分，累加到分数中。
- 选择末尾处的整数 1 ，[1] ，得 1 * 1 = 1 分，累加到分数中。
总分数为 9 + 4 + 1 = 14 。
示例 2：
输入：nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
输出：102
解释：一种最优解决方案如下：
- 选择开头处的整数 -5 ，[-5,-3,-3,-2,7,1] ，得 -5 * -10 = 50 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-3,-2,7,1] ，得 -3 * -5 = 15 分，累加到分数中。
- 选择开头处的整数 -3 ，[-3,-2,7,1] ，得 -3 * 3 = -9 分，累加到分数中。
- 选择末尾处的整数 1 ，[-2,7,1] ，得 1 * 4 = 4 分，累加到分数中。
- 选择末尾处的整数 7 ，[-2,7] ，得 7 * 6 = 42 分，累加到分数中。
总分数为 50 + 15 - 9 + 4 + 42 = 102 。
解题思路（二维动态规划）
求最大分数可以理解为选取nums的前i个数与选取nums的后j个数进行分数操作
用dp[i][j]表示选取前i个数与选取nums的后j个数进行分数操作产生的最大值
dp[i][j]的状态可以由dp[i][j-1]+当前nums末尾数字*当前multipliers或dp[i-1][j]+当前nums开头数字*当前multipliers得来
选取第三步的较大值作为dp[i][j]
判断边界条件，dp[0][0]=0,dp[i][0]=dp[i-1][0]+nums[i-1]*multipliers[i-1],dp[0][j]=dp[0][j-1]+nums[nums.size()-j]*multipliers[j-1];
从dp[i][j]中选取i+j=m的最大值即为结果
细节：注意i+j<=multipliers.size(),即i+j<=m，注意multipliers的实时首数字应当是multipliers[i+j-1]
class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
         int  dp[1003][1003];//选前i个，和后j个与multipliers相乘
        dp[0][0]=0;
        for(int i=1;i<=multipliers.size();++i) dp[i][0]=dp[i-1][0]+nums[i-1]*multipliers[i-1];
        for(int j=1;j<=multipliers.size();++j) dp[0][j]=dp[0][j-1]+nums[nums.size()-j]*multipliers[j-1];
        for(int i=1;i<=multipliers.size();++i){
            for(int j=1;j<=multipliers.size()-i;++j){//注意此处要保持i+j<=multipliers.size(),即i+j<=m
                dp[i][j]=max(dp[i][j-1]+nums[nums.size()-j]*multipliers[i+j-1],dp[i-1][j]+nums[i-1]*multipliers[i+j-1]);//注意此处multipliers的首数字应当是multipliers[i+j-1
         int ans=INT_MIN;
        for(int i=1;i<=multipliers.size();++i){
            ans=max(ans,dp[i][multipliers.size()-i]);
        return ans;
复制代码