用于括起表达式以最大化其值的算法

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).