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

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

分析

A[i,j]

从较短范围到较大范围的元素的计算更加容易。的算法如下：

# Initialization of single valuesfor i in 0, ..., n-1:  A[i,i] = V[i]# Iterate through number of operationfor 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)

。