最大化算术表达式

我想要最大化表达式5-8+7*4-8+9 并且在分割后回答是200 (5 − ((8 + 7) × (4 − (8 + 9))))。最大化算术表达式

它可以通过使用Matrix-chain multiplication算法来解决。它给出正确答案，如果表达式仅具有 '+' 和 '*' 算子

Let's take expression 5+2*4 
    1 2 3 
    1 5 7 28 
    2 - 2 8 
    3 - - 4

这是一个3×3矩阵，其中（1,1）是5，（2,2）是2和（3,3 ）为4 如果我想知道M [1] [2]或M [1] [3]然后

M [1] [2] = M [1] [1] O M [ 2] [2] [2]

M [1] [3] = max（M [1] [1] o M [2] [3]，M [1] [2] ）

有人可以帮我找到' - '操作符的正确方法。

不确定它是否可以用你的算法解决，但这里是我将如何解决它。

假设你必须简化一些表达式：a # b # C# d # e，其中＃是一些操作（＃可以是不同的）。我会用递归（和记忆）来处理它。在递归的第一步骤中，我会尝试在每一个可能位置插入括号和该表达之后计算表达式：

所以你基本上只是将5个运算符表达式减少为4个运算符表达式。如果2个表达式相同，则记忆将会有帮助。只有一个数字时，您可以完成递归（在这种情况下，您将其与最大值进行比较并更新为最大值）。

请注意，对于你的5运算符表达式，你甚至不需要memoization。

2016-06-08 21:02:30

回答