最大化算術表達式

我想要最大化表達式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

回答