### 题目描述 给定一组**正整数**，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。 但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到**最大**的结果，并且返回相应的字符串格式的表达式。你的表达式**不应该含有冗余的括号**。 ### 输入输出 #### 示例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 ``` **说明** 1. 输入数组的长度在 [1, 10] 之间。 2. 数组中每个元素的大小都在 [2, 1000] 之间。 3. 每个测试用例只有一个最优除法解。 ### 题目思路 - 对于该问题，如果想使得除法运算的结果尽可能大，那么**分子尽可能的大，分母尽可能的小**。 #### 思路1——动态规划 采用dp的想法，由短表达式的最大数值得到长表达式的最大数值。通过以上问题的分析，可以看出，需要保存每一段数组的最大值，最小值，最大字符串，最小字符串。这样才可以通过小字符串生成长的字符串。 通过dp[i][j]记录从i——j的字符串，其中需要保存（最大值，最小值，最大字符串，最小字符串）4个变量，因此新建一个类保存这4个属性。 ```python class Node: def __init__(self, min_val=65536, max_val=-1, min_str="", max_str=""): self.min_val = min_val self.max_val = max_val self.min_str = min_str self.max_str = max_str ``` dp[i][j]的最大值和最小值，需要通过dp[i][k]和dp[k+1][j]确定，其中$$k \in [i,j)$$。 **1 最大值的状态转移** 对于dp[i][j]的最大值，需要使得分母尽可能大，分子尽可能小， 寻找$$k_{max} \in [i, j]$$使得 $$max(\frac {dp[i][k].max} {dp[k+1][j].min})$$ **2 最小值的状态转移** 对于dp[i][j]的最小值，需要使得分母尽可能小，分子尽可能大， 寻找$$k_{min} \in [i, j]$$使得 $$min(\frac {dp[i][k.min} {dp[k+1][j].max})$$ **3 生成除法式的状态转移** 根据题目要求不能有冗余的括号，有如下规则： 1. 由于除法从左到右有进行计算，分子不涉及加括号 2. 单个分母无需加括号，多个数字的分母加括号 其中生成最大值字符串如下所示，最小字符串生成同理： ```python if k+1 == end: dp[begin][end].max_str = dp[begin][k].max_str + '/' + dp[k+1][end].min_str else: dp[begin][end].max_str = dp[begin][k].max_str + '/(' + dp[k+1][end].min_str + ')' ``` **确定矩阵的生成次序** 确定了状态转移方程和记录方式之后，下面需要确定整个dp矩阵的生成顺序。 ``` 矩阵初始化，对单个字母的表达式dp[i][i]进行初始化， for i in range(n): dp[i][i] init # 依次生成长度2——n-1的dp结果 for i in range(1, n)： # 依次列举字符串的开头位置 for j in range(n-i): begin = j end = j + i # 依次遍历k属于[i,j) for k in range(begin, end): 寻找最大最小字符串，更新dp数组 # 返回整个字符串的最大值 return dp[0][n-1] ``` **算法复杂度** 时间复杂度：采用3重循环得到dp矩阵，时间复杂度$$O(n^3)$$ 空间复杂度：采用dp[n][n]数组记录，空间复杂度$$O(n^2)$$ #### 思路2——数学推导 如果想获得最大结果，使得分子尽可能大，分母尽可能小。 - 如果分子大，那么分子部分放置一个最大，如果一个以上元素必然就更小了 - 如果分母小，那么连除肯定得到的分母最小，如果加括号，必然导致有元素跑到分子的位置。 由此可见，下列式子可以使得结果最大： $$\frac {nums_0} {nums_1 \div nums_2 \.\.\. \div nums_n}$$ #### 代码实现 ```python class Node: def __init__(self, min_val=65536, max_val=-1, min_str="", max_str=""): self.min_val = min_val self.max_val = max_val self.min_str = min_str self.max_str = max_str class Solution: def optimalDivision(self, nums: List[int]) -> str: # 初始化dp数组 n = len(nums) dp = [[Node() for _ in range(n)] for _ in range(n)] for i in range(n): dp[i][i].min_val = nums[i] dp[i][i].max_val = nums[i] dp[i][i].min_str = str(nums[i]) dp[i][i].max_str = str(nums[i]) # 根据长度进行遍历 for i in range(1, n): # 枚举每次的开始位置 print("len=", i) for j in range(n - i): begin = j end = j + i print(begin, end) # 枚举分割点 max_v = 0 min_v = 65536 for k in range(begin, end): # (0, 2) div = dp[begin][k].max_val / dp[k+1][end].min_val if div > dp[begin][end].max_val: dp[begin][end].max_val = div if k+1 == end: dp[begin][end].max_str = dp[begin][k].max_str + '/' + dp[k+1][end].min_str else: dp[begin][end].max_str = dp[begin][k].max_str + '/(' + dp[k+1][end].min_str + ')' div = dp[begin][k].min_val / dp[k+1][end].max_val if div < dp[begin][end].min_val: dp[begin][end].min_val = div if k+1 == end: dp[begin][end].min_str = dp[begin][k].min_str + '/' + dp[k+1][end].max_str else: dp[begin][end].min_str = dp[begin][k].min_str + '/(' + dp[k+1][end].max_str + ')' return dp[0][n-1].max_str # def optimalDivision(self, nums: List[int]) -> str: # if len(nums) == 1: # return str(nums[0]) # elif len(nums) == 2: # return str(nums[0]) + '/' + str(nums[1]) # res = str(nums[0]) + '/(' # for i in range(1, len(nums)-1): # res += str(nums[i]) + '/' # res += str(nums[-1]) + ')' # return res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复