来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/optimal-division
题目描述
给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。
但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。
示例：
输入: [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, 10] 之间。
数组中每个元素的大小都在 [2, 1000] 之间。
每个测试用例只有一个最优除法解。
解题思路
首先，需要求数值最大，那么需要分子最大分母最小，由于数组中所有数都大于1，并且所有运算均为除法，所以当第一个数为分子的时候，分子最大，接下来需要分母最小，在分母的位置，同样，由于除数均大于0，所以一直连除分母最小，那么将第一个数之后的数全部使用括号括起来就好了。
此题同样也可用动态规划来做，dp[i][j] 中，表示 i 到 j 中所有的信息，包括最大值，最小值，和括号情况，通过一个结构体来记录。状态转移方程为 dp[i][j].max = max(dp[i][k].max / dp[k + 1][j].min) 和 dp[i][j].min= max(dp[i][k].min/ dp[k + 1][j].max ),其中k是i和j之间的数。
代码展示
数学方法：
class Solution { public: string optimalDivision(vector<int>& nums) { int n = nums.size(); if(n == 1) return to_string(nums[0]); else if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]); else { string strRet; strRet += to_string(nums[0]) + "/(" + to_string(nums[1]); for(int i = 2; i < n; i++) { strRet += "/" + to_string(nums[i]); } strRet += ")"; return strRet; } } };
动态规划：
class Solution { public: struct node { string mstrMax, mstrMin; double mdMax = DBL_MIN, mdMin = DBL_MAX; }; string optimalDivision(vector<int>& nums) { int n = nums.size(); vector<vector<node>> dp(n, vector<node>(n)); for(int i = 0; i < n; i++) { dp[i][i].mdMax = dp[i][i].mdMin = nums[i]; dp[i][i].mstrMax = dp[i][i].mstrMin = to_string(nums[i]); } for(int i = 1; i < n; i++) { for(int j = 0; j + i < n; j++) { for(int k = j; k < i + j; k++) { if(dp[j][i + j].mdMax < dp[j][k].mdMax / dp[k + 1][i + j].mdMin) { dp[j][i + j].mdMax = dp[j][k].mdMax / dp[k + 1][i + j].mdMin; if(k + 1 == i + j) { dp[j][i + j].mstrMax = dp[j][k].mstrMax + "/" + dp[k + 1][i + j].mstrMin; } else { dp[j][i + j].mstrMax = dp[j][k].mstrMax + "/(" + dp[k + 1][i + j].mstrMin + ")"; } } if(dp[j][i + j].mdMin > dp[j][k].mdMin / dp[k + 1][i + j].mdMax) { dp[j][i + j].mdMin = dp[j][k].mdMin / dp[k + 1][i + j].mdMax; if(k + 1 == i + j) { dp[j][i + j].mstrMin = dp[j][k].mstrMin + "/" + dp[k + 1][i + j].mstrMax; } else { dp[j][i + j].mstrMin = dp[j][k].mstrMin + "/(" + dp[k + 1][i + j].mstrMax + ")"; } } } } } return dp[0][n - 1].mstrMax; } };
运行结果
![[leetcode] 最优除法 小思维](https://ucc.alicdn.com/pic/developer-ecology/767d514cafa14c6089b06cff6a1d36ad.png?x-oss-process=image/resize,h_160,m_lfit)
