如何使用递归最大化和最小化数学表达式？

Question

表达式由数字 (0-9) 组成，由两个运算符“*”和“+”之一分隔。字符之间没有空格。

示例：1+2*3+4*5

我们需要在适当的地方用括号找出最大和最小值。

最大值：105 = (1+2)*(3+4)*5

最小值：27 = 1+2*3+4*5

我正在寻找一种递归的方法吗？任何想法将不胜感激。

Answer 1

最小化:

解题思路：与其考虑怎么加括号，不如想想最后一个操作是哪个。让我们写一个递归函数minimize(expr)。它应该做什么？如果给它一个数字，它应该只是 return 它。否则，我们可以遍历其中的所有运算符，为运算符左右的部分表达式调用 minimize 并合并结果。现在我们只需要选择最小的值。

这是一些伪代码：

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

最大化：

几乎相同，但我们应该在每一步取最大值而不是最小值。

为什么是正确的？当我们对非负数进行乘法和加法时，操作数越大（越小），结果就越大（越小）。

我们也可以使用记忆来避免对同一个表达式重新计算两次（或更多次）的结果并获得多项式时间复杂度。

如何使用递归最大化和最小化数学表达式？

How do I maximise and minimize the mathematical expression using recursion?

algorithm

recursion

dynamic-programming