这是前段时间问我的一个面试问题:
Suppose you are given an expression E= x1 y1 x2 y2....yn-1 xn.
Where Xi belong to natural number and Yi belongs to { +,*}
you need to parenthesize such that it maximize the value of E ?
我能够朝动态规划的方向思考并将其与matrix chain multiplication problem联系起来, 但一直坚持推导这个关系的确切递归关系。
此外，后续问题让我的情况变得更加复杂:
Let's change Yi to { +,-,*,/}, then how to maximize E? Now add % operator in that set..then how to maximize E?
关于如何处理和构建解决方案的解释会很棒。
最佳答案
我认为与矩阵乘法算法的相同关系会起作用。
我们要计算的函数是
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 以最小化区间内的值。
如果我们允许减法，那么我们将需要考虑正数和负数d。如果您跟踪最大正数、最小正数、最大负数和最小负数，我认为您应该能够获得所需的任何值。也许有一种替代方案需要更少的计算。
我没有停下来思考 % 的含义。对于初学者，它如何处理来自 / 的非整数结果？
关于algorithm - 动态规划 : maximize value of arithmetic expression using parenthesis，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24744491/