feat: $1770

robot · robot · commit 97a3e0a09e6f · 2022-08-12T23:36:19.000+08:00
diff --git a/README.md b/README.md
@@ -412,7 +412,8 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [1631. 最小体力消耗路径](./problems/1631.path-with-minimum-effort.md)
 - [1658. 将 x 减到 0 的最小操作数](./problems/1658.minimum-operations-to-reduce-x-to-zero.md)
 - [1697. 检查边长度限制的路径是否存在](./problems/1697.checking-existence-of-edge-length-limited-paths.md)
-- [1737. 满足三条件之一需改变的最少字符数](./problems/1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md)
+- [1737. 满足三条件之一需改变的最少字符数](./problems/1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md) 👍
+- [1770. 执行乘法运算的最大分数](./problems/1770.maximum-score-from-performing-multiplication-operations.md) 👍 91
 - [1834. 单线程 CPU](./problems/1834.single-threaded-cpu.md)
 - [1899. 合并若干三元组以形成目标三元组](./problems/1899.merge-triplets-to-form-target-triplet.md) 👍
 - [1904. 你完成的完整对局数](./problems/1904.the-number-of-full-rounds-you-have-played.md)
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -261,6 +261,7 @@
   - [1658. 将 x 减到 0 的最小操作数](./problems/1658.minimum-operations-to-reduce-x-to-zero.md)
   - [1697. 检查边长度限制的路径是否存在](./problems/1697.checking-existence-of-edge-length-limited-paths.md)
   - [1737. 满足三条件之一需改变的最少字符数](./problems/1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md) 👍
+  - [1770. 执行乘法运算的最大分数](./problems/1770.maximum-score-from-performing-multiplication-operations.md)👍 91
   - [1834. 单线程 CPU](./problems/1834.single-threaded-cpu.md)
   - [1899. 合并若干三元组以形成目标三元组](./problems/1899.merge-triplets-to-form-target-triplet.md) 👍
   - [1904. 你完成的完整对局数](./problems/1904.the-number-of-full-rounds-you-have-played.md)
diff --git a/problems/1770.maximum-score-from-performing-multiplication-operations.md b/problems/1770.maximum-score-from-performing-multiplication-operations.md
@@ -0,0 +1,171 @@
+## 题目地址(1770. 执行乘法运算的最大分数)
+
+https://leetcode.cn/problems/maximum-score-from-performing-multiplication-operations/
+
+## 题目描述
+
+```
+给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。
+
+初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：
+
+选择数组 nums 开头处或者末尾处 的整数 x 。
+你获得 multipliers[i] * x 分，并累加到你的分数中。
+将 x 从数组 nums 中移除。
+
+在执行 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 。
+
+
+ 
+
+提示：
+
+n == nums.length
+m == multipliers.length
+1 <= m <= 103
+m <= n <= 105
+-1000 <= nums[i], multipliers[i] <= 1000
+```
+
+## 前置知识
+
+- 动态规划
+- 区间动态规划
+
+## 公司
+
+- 暂无
+
+## 思路
+
+这是一个典型的区间 DP 问题。
+
+直接套用区间 DP 的公，定义 DP[i][j] 为考虑区间 nums[i:j] 的情况下， 所能获得的最大分数。
+
+那么我们有两个选择， 取左端点或者取右端点，这两种选择取最大值即可。同时需要一个变量记录当前是第几步操作， 以便知道要乘以多少。
+
+这样 dp[i][j][steps] 就表示考虑区间 nums[i:j] 的情况下当前是第 steps 步， 所能获得的最大分数。
+
+```py
+class Solution:
+    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
+        @cache
+        def dp(i, j, steps):
+            if steps == len(multipliers): return 0
+            return max(dp(i + 1, j, steps + 1) + multipliers[steps] * nums[i], dp(i, j - 1, steps + 1) + multipliers[steps] * nums[j])
+        return dp(0, len(nums) - 1, 0)
+```
+
+上面代码非常好写，复杂度为 $O(m*n^2)$但是会严重超时。代入题目中的数据 m 为 10^3, n 为 10 ^ 5，那么整体就是 $10^13$， 远远大于 $10^7$ 这个临界值。
+
+注意到 steps 其实可以根据 i 和 j 推导出来。因为每一步我们必定要选择一次，这是关键。那么我们当前选择了多少就可以根据 i 和 j 推导出来， 这样就可以降低到二维 dp[i][j]。代码：
+
+```py
+class Solution:
+    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
+        @cache
+        def dp(i, j):
+            steps = len(nums) - (j - i + 1)
+            if steps == len(multipliers): return 0
+            return max(dp(i + 1, j) + multipliers[steps] * nums[i], dp(i, j - 1,) + multipliers[steps] * nums[j])
+        return dp(0, len(nums) - 1)
+```
+
+不过代入后还是远远大于 $10^7$ 这个临界值。
+
+小技巧，下面的代码可以通过，不过也不推荐。
+
+```py
+class Solution:
+    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
+        @cache
+        def dp(i, j):
+            steps = len(nums) - (j - i + 1)
+            if steps == len(multipliers): return 0
+            return max(dp(i + 1, j) + multipliers[steps] * nums[i], dp(i, j - 1,) + multipliers[steps] * nums[j])
+        ans = dp(0, len(nums) - 1)
+        dp.cache_clear()
+        return ans
+```
+
+这里要使用到一种技巧 - 维度选择。
+
+我们可以换一种状态定义方式，即思考 mutlipiers， 因为它的数据量小（题目给的是 10 ^ 3）。
+
+实际上，我们可以定义 dp[i][j] 为选择 nums 前 i 项目和 nums 后 j 项目可以获得的最大分数（题目限制了只能取左右两端）。但是注意到 i 和 j 一定是要小于 m 的， 因为不妨直接枚举到 m 即可， 而不需要枚举到 n。
+
+显然这种方式枚举的时间复杂度为 $O(m^2)$，代入题目大概是 $10^6$ , 小于临界值 $10^7$。
+
+## 关键点
+
+- 维度选择
+- 降维
+
+## 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```python
+
+class Solution:
+    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
+        n,m=len(nums),len(multipliers)
+        dp=[[float('-inf')]*(m+1) for _ in range(m+1)]
+        dp[0][0]=0
+        ans=float('-inf')
+        for i in range(1,m+1): # 枚举长度
+            for l in range(i+1): # 枚举左侧取了 l 个
+                r = i - l # 右侧取的就是总数 -  左边取的
+                dp[l][r]=max(dp[l][r],dp[l-1][r]+nums[l-1]*multipliers[i-1], dp[l][r-1]+nums[-r]*multipliers[i-1])
+                if i == m: ans=max(ans,dp[l][r])
+        return ans
+
+
+```
+
+**复杂度分析**
+
+令 n 为数组长度。
+
+- 时间复杂度：$O(n^2)$
+- 空间复杂度：$O(n^2)$
+
+> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
+
+## 其他
+
+大家也可以看下[力扣国际站的官方题解](https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/solution/)
