执行乘法运算的最大分数
2021-02-22 本文已影响0人
phusFuNs
题目：
[1770. 执行乘法运算的最大分数]
给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。
初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：
选择数组 nums 开头处或者末尾处 的整数 x 。
你获得 multipliers[i] * x 分，并累加到你的分数中。
将 x 从数组 nums 中移除。
在执行 m 步操作后，返回 最大 分数。
链接：https://leetcode-cn.com/problems/maximum-score-from-performing-multiplication-operations
解题方法
定义二维数组dp[m + 1][m + 1]。dp[i][j]：表示nums数组中前i个数和后j个数组成的最大分数。
base case：
dp[0][0] = 0;
dp[i][0]：此状态表示nums数组中前i个数和后0个数组成的最大分数，此状态只可能由dp[i - 1][0]转移得到。
dp[0][j]：此状态表示nums数组中前0个数和后j个数组成的最大分数，此状态只可能由dp[0][j - 1]转移得到。
dp[i][j]：该状态表示nums数组中前i个数和后j个数组成的最大分数，可能由状态
dp[i - 1][j]和状态dp[i][j - 1]转移得到，取其中得分最大的一个。
遍历所有可能的组合（满足i + j = m）获得最大得分。
代码
class Solution {
public int maximumScore(int[] nums, int[] multipliers) {
int n = nums.length,m = multipliers.length;
int[][] dp = new int[1000 + 5][1000 + 5];
dp[0][0] = 0;
for (int i = 1;i <= m;++i) dp[i][0] = dp[i - 1][0] + nums[i - 1] * multipliers[i - 1];
for (int j = 1;j <= m;++j) dp[0][j] = dp[0][j - 1] + nums[n - j] * multipliers[j - 1];
for (int i = 1;i <= m;++i){
for (int j = 1;i + j <= m;++j){
dp[i][j] = Math.max(dp[i - 1][j] + nums[i - 1] * multipliers[i + j - 1],dp[i][j - 1] + nums[n - j] * multipliers[i + j - 1]);
}
}
int ans = Integer.MIN_VALUE;
for (int i = 0;i <= m;++i) ans = Math.max(ans,dp[i][m - i]);
return ans;
}
}
