如何使用遞歸最大化和最小化數學表達式？

Question

表達式由兩個運算符'*'和'+'之一分開的數字（0-9）組成。角色之間沒有空格。

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

我們需要找出最大的，我們可以通過在適當的地方使用括號得到最小值。

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

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

我正在尋找一種遞歸的方式做到這一點？任何想法，將不勝感激。

Answer 1

最小化：

解決方案的主要思想：不是想怎麼加括號，讓我們想想哪些操作是最後一個。我們來寫一個遞歸函數minimize(expr)。它應該做什麼？如果給出一個數字，它應該返回它。否則，我們可以迭代其中的所有運算符，請將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 

最大化：

幾乎相同，但我們應該在每一步走，而不是最大最小。

爲什麼它是正確的？當我們乘加非負數時，操作數越大（越小），結果越大（越小）。

我們還可以使用記憶來避免兩次（或更多次）同一表達式的重新計算結果並獲得多項式時間複雜度。