欢迎阅读 欢迎来到「最优除法」题解之旅本文将带你从“通过添加括号改变除法优先级”这一算术问题出发深入理解贪心算法 数学推导的精妙之处并掌握如何利用连除性质快速构造出使结果最大的表达式。在开始之前建议你先了解题目背景这是 LeetCode 553 题给定一个正整数数组nums相邻整数按顺序进行浮点除法如[2,3,4]表示2/3/4你可以在任意位置添加括号改变运算顺序目标是使最终结果最大并以字符串形式返回对应表达式不含冗余括号。本质上这是一个关于除法优先级的最优化问题。明确学习目标掌握贪心推导的结论——对于nums[0] / nums[1] / ... / nums[n-1]最大结果表达式为nums[0] / (nums[1] / nums[2] / ... / nums[n-1])即把除了第一个数以外的所有数用括号括起来并连续相除。理解为什么这样构造能最大化因为除法中分母越小结果越大而将后面的数相除会使分母最小化并熟练处理边界情况n1或n2时无需括号。一、题目553. 最优除法 - 力扣LeetCode二、做题思路1. 问题分析前置分析给定一个正整数数组nums要求通过添加括号改变浮点除法的运算顺序使得整个表达式的值最大。基础形式是nums[0] / nums[1] / nums[2] / ...括号可以改变除法的结合性。核心观察由于所有数均为正整数且数组长度至少为 2将第一个数作为分子其余所有数作为分母并将分母部分整体括起来能使结果最大化。2. 贪心策略核心决策规则特殊情况若n 1直接返回该数。特殊情况若n 2返回nums[0] / nums[1]无需括号。一般情况n 3构造表达式nums[0] / (nums[1] / nums[2] / ... / nums[n-1])这等价于nums[0] * nums[2] * ... * nums[n-1] / nums[1]即分子为第一个数乘以除第二个数以外的所有数分母仅为第二个数。因为所有数 2这种形式使得分母尽可能小仅一个数从而结果最大。3. 正确性说明简单版本设数组为a, b, c, d, ...所有数 ≥ 2。原始表达式a / b / c / ...默认从左到右相当于a / (b * c * ...)。在分母中加入乘法会扩大分母从而减小整体值。为了最大化结果我们应尽可能让分母变小即让尽量少的数留在分母。通过添加括号我们可以将a以外的所有数“压缩”到分子上具体做法是a / (b / c / d / ...)而(b / c / d / ...)等价于b / (c * d * ...)但由于括号内的除法会变为乘法最终结果化为a * c * d * ... / b这时分母仅剩b是可能的最简形式。这种形式是唯一的全局最大值因为任何其他加括号方式都会让至少一个数除b外留在分母或让b移到分子导致分母变大或分子变小结果不会更大。4. 实现细节边界防护处理n 1和n 2的特殊情况。对于n 3构造字符串先添加nums[0] /(然后循环添加nums[1]到nums[n-2]并用/连接最后添加nums[n-1] )。。5. 返回值目标映射返回构造好的最优表达式字符串即满足最大值的表达式。四、代码class Solution { public: string optimalDivision(vectorint nums) { int n nums.size(); // 1. 特殊情况只有一个数时直接返回该数无除法 if (n 1) { return to_string(nums[0]); } // 2. 特殊情况只有两个数时直接相除无需括号 if (n 2) { return to_string(nums[0]) / to_string(nums[1]); } // 3. 一般情况n gt; 3 // 数学结论为了使除法表达式结果最大应该将 nums[0] 作为分子 // 其余所有数作为分母并且将分母部分用括号括起来 // 即 nums[0] / (nums[1] / nums[2] / ... / nums[n-1]) // 这样等价于 nums[0] * nums[2] * ... * nums[n-1] / nums[1] // 是能得到的最大值因为所有数都为正整数。 string ret; // 构造nums[0] / ( ret to_string(nums[0]) / (; // 中间部分nums[1] / nums[2] / ... / nums[n-2]最后一项单独处理 for (int i 1; i lt; n - 1; i) { ret to_string(nums[i]) /; } // 最后一项nums[n-1] ) ret to_string(nums[n - 1]) ); // 4. 返回构造好的最优表达式字符串 return ret; } };五、流程图​六、正确性说明详细版步骤 1符号与问题建模---------------------------------------------------- | 输入正整数数组 nums [a₁, a₂, ..., aₙ] | | 操作在相邻数之间插入除号可加任意括号改变优先级| | 目标使整个表达式的值最大返回对应字符串 | ---------------------------------------------------- | v ---------------------------------------------------- | 贪心策略当 n ≥ 3 时构造表达式 | | a₁ / (a₂ / a₃ / ... / aₙ) | | 即a₁ 作为分子其余所有数放在一个括号内连除。 | | 该表达式等价于 a₁ * a₃ * a₄ * ... * aₙ / a₂。 | | 贪心实质通过括号将 a₂ 单独放在分母最底层 | | 而 a₃..aₙ 变成乘数最大化分子/分母比值。 | ----------------------------------------------------设数组元素为a₁, a₂, ..., aₙ图二中用 a,b,c,d,e,f 表示。由于所有数均为正整数且原题无限制但图二提到 ≥2这使结论更强除法运算等价于乘以倒数因此加括号的本质是决定哪些数乘到分子、哪些乘到分母。贪心结论最优表达式为a₁ / (a₂ / a₃ / ... / aₙ)即把第一个数作为分子剩余所有数作为分母并整体括起来。步骤 2关键性质 —— 最优表达式结构反证法与不等式---------------------------------------------------- | 性质 1任意加括号的表达式都可以化为 | | a₁ * X / Y 的形式其中 X 是 a₃..aₙ 中某些数的 | | 乘积Y 是 a₂..aₙ 中某些数的乘积且 a₂ 必然在 Y | | 中因为 a₁ 是第一个数除号紧跟在 a₁ 后。 | | 反证若 a₂ 不在分母则 a₂ 变为乘数会增大 | | 分子但 a₂ 右侧的数会相应调整总效果是 | | 分母变小但无法超过将 a₂ 单独放分母的极端情况。 | ---------------------------------------------------- | v ---------------------------------------------------- | 性质 2核心不等式对于任意 i ≥ 3 | | 将 a_i 放在分母中会除以 a_i而放在分子中会乘以 | | a_i。由于 a_i ≥ 2图二条件乘比除大 | | 因此为了最大化应让尽可能多的数除 a₂ 外 | | 进入分子。但 a₂ 必须留在分母因为紧跟 a₁ 的除号 | | 必然将 a₂ 置于分母所以最佳是让 a₃..aₙ 全在 | | 分子即表达式为 a₁ / (a₂ / a₃ / ... / aₙ)。 | | 不等式示意若将某个 a_i (i≥3) 放到分母则值 | | 变为原来的 1/a_i² 倍因为原来乘 a_i现在除 | | a_i显然减小。 | ----------------------------------------------------详细论证性质1结构分解任何加括号的除法表达式由于第一个数是a₁且第一个运算符是除号所以a₁必然作为分子。其后的所有数通过括号和除法组织最终可以看作a₁乘以某些数的乘积再除以某些数的乘积。a₂必然出现在分母中因为a₁ / a₂是最先形成的除法关系无论括号如何a₂不能变为乘数除非有括号将其与后续数组合但a₁除以的是一个整体该整体包含a₂且a₂在分母位置。性质2最优化选择对于任意i ≥ 3将a_i放在分子比放在分母更优。若当前a_i在分母将其移到分子通过调整括号表达式值会乘以a_i^2因为原来除以a_i现在乘以a_i。由于a_i ≥ 2a_i^2 1值严格增大。因此最优解必须让所有a₃..aₙ都在分子。唯一必须留在分母的是a₂故最优形式为a₁ * a₃ * a₄ * ... * aₙ / a₂即a₁ / (a₂ / a₃ / ... / aₙ)。步骤 3归纳证明 —— 贪心构造即为全局最优---------------------------------------------------- | 初始n 个数已确定 a₁ 为分子。 | | 归纳假设对于后缀 a₂..aₙ最优分母构造是 | | 让 a₂ 单独留在分母其余数通过嵌套括号转化为乘数。 | ---------------------------------------------------- | v ---------------------------------------------------- | 处理 a₂它必须留在分母因为紧跟 a₁ 的除号。 | | 处理 a₃..aₙ由性质2每个都应进入分子。 | | 构造括号a₂ / a₃ / ... / aₙ 整体作为分母 | | 因为连除等价于 a₂ / (a₃ * ... * aₙ)即 a₂ 在 | | 分母a₃..aₙ 实际上变为乘数因为除以一个除式 | | 等于乘以该除式倒数的乘积。 | | 最终表达式 a₁ / (a₂ / a₃ / ... / aₙ) 达到最大。 | ---------------------------------------------------- | v ---------------------------------------------------- | 结论该贪心策略得到最大表达式值且字符串为 | | a₁/(a₂/a₃/.../aₙ)去掉冗余括号后返回。 | ----------------------------------------------------终止当处理完所有数得到表达式即为最大值。若n1或2直接返回无需括号。 闭幕 恭喜你完成了「最优除法」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题采用贪心策略对于长度大于 2 的数组最优表达式为nums[0] / (nums[1] / nums[2] / ... / nums[n-1])。为什么这样能让结果最大你能从除法的数学性质例如除以一个分数等于乘以它的倒数来解释吗代码中分别处理了n 1和n 2的情况。如果长度为 1 或 2 时也套用通用括号形式会得到什么结果为什么需要单独处理当n 3时括号从第二个数开始括到最后一个数。为什么不在第一个数后面直接加括号例如(nums[0]/nums[1])/nums[2]与nums[0]/(nums[1]/nums[2])哪种更大用例子验证一下。延伸挑战将题目改为求表达式的最小值你应该如何调整括号位置只需要改变哪里的策略如果要求返回最大值对应的数值而不是表达式代码需要做哪些修改如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨