执行乘法运算的最大分数

题目：

[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;
    }
}

参考链接：https://leetcode-cn.com/problems/maximum-score-from-performing-multiplication-operations/solution/dong-tai-gui-hua-er-wei-zhuang-tai-ding-slg21/