performance - 将表达式括起来以最大化其值的算法

Question

我在查找有关动态规划的问题时发现了这一点。给你一个形式为 V0 O0 V1 O1 .... Vn-1 的无括号表达式

我们必须在使整个表达式的值最大化的地方放置括号。

V 是操作数，O 是运算符。在问题的第一个版本中，运算符可以是 * 和 +，并且操作数是正数。问题的第二个版本是完全通用的。

对于第一个版本，我提出了 DP 解决方案。

解决方案 -A[] = 操作数数组B[] - 运算符数组T(A[i,j]) - 表达式的最大值 T(A[0,n-1]) = 所有 i 的最大值 {(T(A[0,i]) Oi T(A[i+1,n-1]))}

边界情况很简单(当 i = j 时)。我需要以下方面的帮助 -分析该算法的运行时间。如果有更好的。

Answer 1

更容易分析A[i,j]元素从较短范围到较长范围的计算。算法看起来像:

# Initialization of single values
for i in 0, ..., n-1:
  A[i,i] = V[i]

# Iterate through number of operation
for d in 1, ..., n-1:
  # Range start
  for i in 0, ..., n-1-d:
    j = i + d
    A[i,j] = max( A[i,x] O_x A[x+1,j] for x in i, ..., j-1)

print 'Result', A[0,n-1]

因为 A[] 可以用常量时间访问(数组)来实现，所以算法是 O(n^3)。