这是前一段时间问我的一个面试问题:
我能够在动态规划的方向上思考并将其与 matrix chain multiplication problem 联系起来，但一直坚持推导出这个关系的确切递归关系。
此外，后续问题只会让我的情况复杂化:
关于如何处理和构建解决方案的解释会很棒。
最佳答案
我认为与矩阵乘法算法的相同关系将起作用。
我们试图计算的函数是
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/