LeetCode 1770 题解执行乘法运算的最大分数——区间 DP 的维度选择与降维实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以本仓库 problems/1770.maximum-score-from-performing-multiplication-operations.md 题解文档为核心骨架展开结合仓库 动态规划专题 中的区间 DP 理论完整还原一道经典两端取数 加权得分问题的三种动态规划递进方案从直观的带步数维度的区间 DP到利用步数可推导性完成降维再到利用 multipliers 数据规模更小这一特点进行维度选择最终得到 O(m²) 的可行解法。读完本篇你将掌握状态维度怎么选、何时降维、如何判断复杂度是否可接受这套在区间 DP 题中反复使用的实战方法论。题目描述给你两个长度分别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 。注意示例 2 中nums存在负数multipliers也有负数因此每一步贪心地选绝对值最大是行不通的必须枚举所有取法取最优这正是动态规划登场的原因。提示n nums.lengthm multipliers.length1 m 10^3m n 10^5-1000 nums[i], multipliers[i] 1000约束中最关键的信息是m只有10^3量级而n高达10^5。这个不对称的数据规模直接决定了后续的优化方向。前置知识动态规划区间动态规划本仓库的 thinkings/dynamic-programming.md 对区间 DP 给出了精确定义令状态f(i,j)表示将下标位置i到j的所有元素合并能获得的价值的最大值转移形如f(i,j) max{f(i,k) f(k1,j) cost}。而本类从数组两端同时取数的题目正是区间 DP 的经典形态——该专题文档在什么时候用记忆化递归一节中特别指出从数组两端同时进行遍历的时候使用记忆化递归方便其实也就是区间 DP并列举了石子游戏等同型题目。思路分析直觉两端取数的区间 DP题目每一步只能取nums当前区间的左端点或右端点因此每一步操作后剩余的可选元素仍然是一个连续的区间nums[i:j]下标闭区间。这是一个典型的区间 DP问题。按照考虑区间nums[i:j]的情况下所能获得的最大分数来定义状态每一步有两个选择取左端点或取右端点两者取最大值即可。同时还需要一个变量记录当前是第几步操作以便知道本轮要乘的乘数multipliers[steps]是多少。方案一带步数维度的三维区间 DP定义dp[i][j][steps]表示考虑区间nums[i:j]、当前是第steps步操作时所能获得的最大分数。转移方程非常直白取左端点dp[i1][j][steps1] multipliers[steps] * nums[i]取右端点dp[i][j-1][steps1] multipliers[steps] * nums[j]两者取max递归出口是steps len(multipliers)时返回 0所有乘数用完。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^3 * (10^5)^2 10^13量级远远大于10^7这个经验临界值通常认为单次评测可接受的状态枚举量级上限。方案二利用步数可推导性降维到二维注意到一个关键事实每一步操作我们必定要选择一次。因此当前已经取了多少个元素完全可以由区间[i, j]的长度推导出来steps len(nums) - (j - i 1)即区间越短说明已经取走的元素越多。这样steps就不再是独立维度三维 DP 可以降到二维dp[i][j]。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)不过代入数据后状态数依然是O(n^2)i、j的取值组合数是n^2量级还是远远大于10^7这个临界值仍然无法通过。小技巧下面的代码在 Python 中可以利用cache只缓存实际访问到的状态而非全量n^2个状态配合cache_clear()清理缓存偶尔可以通过但并不推荐——它没有从根本上改善最坏复杂度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方案三维度选择——围绕数据规模更小的 multipliers 定义状态到这里前面两种方案失败的根源是状态围绕nums定义而n高达10^5。这里要使用一个非常重要的技巧——维度选择。换个角度思考既然乘数数组multipliers的数据量小题目给的是10^3为什么不围绕它来定义状态由于题目限制只能取nums左右两端实际上我们可以定义dp[i][j]为选择nums前i项和nums后j项可以获得的最大分数。这里有个关键的观察i和j一定都要小于等于m因为总共只执行m步操作最多只能从左侧取m个、从右侧取m个因此不需要枚举到n直接枚举到m即可。这彻底绕开了n 10^5的规模瓶颈。枚举方式的时间复杂度为O(m^2)代入题目大概是(10^3)^2 10^6小于临界值10^7可以通过。更具体地说第k步操作完成后i j k恒成立——共取走了k个元素其中i个来自左侧、j个来自右侧。于是可以用按步数i j分层 枚举左侧取了几个的方式做迭代 DP最终答案在i j m那一层产生。关键点维度选择当某一维数据规模远大于另一维时围绕规模小的一维定义状态降维利用每步必取一个的约束用区间长度反推已执行步数消除多余维度边界处理用float(-inf)初始化使非法转移不影响结果。代码实现语言支持Python3class 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对代码的几点实现说明可从源码结构直接观察到dp是(m1) × (m1)的表格全部初始化为float(-inf)仅dp[0][0] 0为合法起点转移只看两条入边最后一步取的是左侧第l个元素nums[l-1]或右侧第r个元素nums[-r]Python 负索引即从尾部倒数当l 0或r 0时dp[l-1][r]、dp[l][r-1]会借助 Python 负索引落到-inf初始化的边界行/列配合-inf初始化非法状态不会污染答案——这是一个值得留意的边界处理技巧因为i j 步数外层循环i已走步数实际就是对角线枚举最终取i m层即恰好执行完m步的最大值。复杂度分析令n为nums长度、m为multipliers长度时间复杂度O(m^2)——两层循环均以m为界代入m 10^3约为10^6状态满足评测时限要求空间复杂度O(m^2)——dp表大小为(m1) × (m1)。原题解文档的复杂度分析写作O(n^2)这里结合最终代码按实际枚举范围修正为O(m^2)代码中的两层循环上限均为m与n无关这也是维度选择优化能成立的根本原因。与仓库理论的呼应区间 DP 的两端取数形态本仓库 thinkings/dynamic-programming.md第 686 行起对区间 DP 归纳了三个特点与本题的求解思路一一对应合并将两个或多个部分进行整合当然也可以反过来——本题反过来看就是从完整区间逐步拆掉两端特征能将问题分解为能两两合并的形式——每步二选一取左/取右天然是二叉决策树求解对整个问题设最优值枚举合并点——本题的合并点即每次取走的端点位置。该专题文档还指出从数组两端同时进行遍历的时候使用记忆化递归方便本质就是区间 DP并推荐了 877. 石子游戏、312. 戳气球 等同类题目——它们共享两端取数/两端合并 区间状态的骨架本题的维度选择技巧同样适用于那些题目。总结1770. 执行乘法运算的最大分数的价值不在于 DP 本身有多难而在于它完整演示了一条从写得出来到跑得过的优化链路先写出正确性优先的版本三维区间 DPdp[i][j][steps]思路最直白识别冗余维度steps可由区间长度推出降维到dp[i][j]发现瓶颈在数据规模n 10^5导致无论怎么降维都超时做维度选择改由小规模的m定义状态dp[i][j]左侧取i个 右侧取j个复杂度降到O(m^2)通过。这正是维度选择与降维两大关键点在真实题目中的完整实战当状态里某一维的数据规模远小于另一维时优先围绕小维定义状态。建议结合 动态规划专题 中关于记忆化递归与迭代 DP 的对比第 731 行起从数组两端同时进行遍历的时候使用记忆化递归方便一起阅读并把 877. 石子游戏 作为巩固练习。本题收录于仓库 README.md 与 SUMMARY.md 的问题列表problems/1770.maximum-score-from-performing-multiplication-operations.md可作为刷题插件学习路线中区间 DP / 两端取数类目的参考例题。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考