algorithm - 无括号算术表达式

Question

算术表达式可以有许多可能的值

有人能帮我吗？

Answer 1

有一个动态规划解决方案。

对于表达式，您可以将其“最外分割点”定义为不在任何括号内的第一个运算符。现在在这个拆分之后，如果它在 a 上+，那么你需要最大化左子表达式和右子表达式；如果是 a -，则最大化左侧并最小化右侧。

您可以使用动态编程或记忆化来实现此算法。记忆很简单：搜索每个分割点，并将答案保存在另一个数据结构中（两个二维矩阵，M[x][y]字符串是表达式的最大值/最小值，从 开始到x结束y）；当数据在矩阵中时，使用它而不是重新计算。

使用动态编程有点棘手，但你可以这样想：

1. 首先，您循环遍历表达式，找到每个连续 2 个值的最大值/最小值，并在它们之间使用运算符（嗯，这是说只是计算它的奇特方式）；
2. 循环遍历表达式，找到每个连续 3 个值的最大值/最小值，它们之间有运算符（对于a ? b ? c，这是通过假设分割点在a和之间来计算的b，并且假设分割点在b和之间c，并存储最大值/这两个的最小值）；
3. 一旦您知道所有k-length 序列的最大/最小值，k + 1使用与步骤 2 中相同的方法计算 -length 序列，直到 k 是数组的长度，并返回 length 的最大值k。

这与具有复杂性的矩阵链乘法算法几乎相同。O(N^3)可以通过推理粗略地证明复杂性：您需要执行循环N - 1次数，每次最多N - 1子序列，并且您需要尝试最多N - 1拆分点。所以，N ^ 3时间复杂度。