动态编程：使用括号使算术表达式的值最大化

Question

这是前段时间问我的面试问题：

假设您得到一个表达式E = x1 y1 x2 y2 .... yn-1 xn。

其中Xi属于自然数，Yi属于{+，*}

您需要括号以使其最大化E的值？

我能够朝着动态编程的方向思考，并且可以将其与矩阵链乘法问题联系起来，但是一直坚持推导这一问题的确切递归关系。

而且，后续问题对我来说使情况复杂化：

让我们将Yi更改为{+，-，*，/}，然后如何最大化E？现在在该集合中添加％运算符。然后如何最大化E？

关于如何解决并为此建立解决方案的解释会很棒。

Answer 1

我认为与矩阵乘法算法的相同关系将起作用。

我们正在尝试计算的函数是

F(i,j) = maximum number that can be computed using Xi ... Xj

基本情况是当我们只有一个数字时：

F(i,i) = Xi

递归的情况是用括号括起来的两个子表达式之间的运算：

F(i,j) = for k = i,j-1, maximize
    F(i,k) Yk F(k+1, j)

我认为，为了使乘数和加数超过正数，我们希望最大程度地增加数字是可行的，因为我们希望两个操作数都尽可能大。

如果我们允许除法，那么我们将希望第二个操作数尽可能小以使结果最大化。在这种情况下，F您不仅需要计算，还需要计算一个类似的函数G，以最小化间隔内的值。

如果我们允许减法，那么我们将需要考虑正数和负数。如果您跟踪大正数，最小正数，最大负数和最小负数，我认为您应该能够获取所需的任何值。也许有替代方法需要较少的计算。

我不停地思考的含义%。对于初学者来说，它与的非整数结果/有何关系？