---

0553. 最优除法

• 标签：数组、数学、动态规划
• 难度：中等

题目链接

• 0553. 最优除法 - 力扣

题目大意

描述：

给定一正整数数组 $nums$，$nums$ 中的相邻整数将进行浮点除法。

• 例如，$nums = [2,3,4]$，我们将求表达式的值 "2/3/4"。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。

要求：

找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

说明：

• 注意：你的表达式不应该包含多余的括号。
• $1 \le nums.length \le 10$。
• $2 \le nums[i] \le 1000$。
• 对于给定的输入只有一种最优除法。

示例：

• 示例 1：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

• 示例 2：

输入: nums = [2,3,4]
输出: "2/(3/4)"
解释: (2/(3/4)) = 8/3 = 2.667
可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。

解题思路

思路 1：数学分析

要使表达式 $nums[0] / nums[1] / nums[2] / ... / nums[n-1]$ 的值最大，我们需要让分子尽可能大，分母尽可能小。

观察：$nums[0]$ 必须作为分子，$nums[1]$ 必须作为分母。要使结果最大，应该让 $nums[1]$ 之后的所有数都作为分母的一部分，即让它们连除。

最优方案：$nums[0] / (nums[1] / nums[2] / ... / nums[n-1])$

这样 $nums[1]$ 之后的所有数都会作为分母，使得分母最小，结果最大。

特殊情况：

• 如果数组长度为 $1$，直接返回 $nums[0]$。
• 如果数组长度为 $2$，返回 $nums[0] / nums[1]$。

思路 1：代码

class Solution:
    def optimalDivision(self, nums: List[int]) -> str:
        n = len(nums)
        
        # 特殊情况
        if n == 1:
            return str(nums[0])
        if n == 2:
            return f"{nums[0]}/{nums[1]}"
        
        # 一般情况：nums[0] / (nums[1] / nums[2] / ... / nums[n-1])
        result = f"{nums[0]}/({nums[1]}"
        for i in range(2, n):
            result += f"/{nums[i]}"
        result += ")"
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n)$，需要遍历数组一次构建字符串。
• 空间复杂度：$O(n)$，字符串的长度为 $O(n)$。