表达式由两个运算符*'和'分隔的数字（0-9）组成+。字符之间没有空格。
例子： 1+2*3+4*5
我们需要找出在适当位置使用方括号可获得的最大值和最小值。
最大值：105 = (1+2)*(3+4)*5
最小值： 27 = 1+2*3+4*5
我正在寻找一种递归的方式吗？任何想法，将不胜感激。
最小化：
解决方案的主要思想是：不用考虑如何添加括号，而是考虑哪个操作是最后一个操作。让我们编写一个递归函数minimize(expr)。应该怎么办？如果给定一个数字，则应将其返回。否则，我们可以遍历其中的所有运算符，在运算符minimize的左侧和右侧调用part表达式并组合结果。现在我们只需要选择最小值即可。
这是一些伪代码：
int minimize(string expr)
if isNumber(expr) then // If it is one number, return it.
return value(expr)
int res = infinity
for int i <- 0 .. lenght expr - 1
if expr[i] == '+' then
res = min(res, minimize(expr[0 .. i - 1]) +
minimize(expr[i + 1 .. length expr - 1])
if expr[i] == '*' then
res = min(res, minimize(expr[0 .. i - 1]) *
minimize(expr[i + 1 .. length expr - 1])
return res
最大化：
几乎相同，但在每一步中我们都应采用最大值而不是最小值。
为什么正确？当我们将非负数相乘并相加时，操作数越大（越小），结果就越大（越小）。
我们还可以使用记忆来避免对相同表达式重复两次（或多次）重新计算结果，并获得多项式时间复杂度。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句