我在查找动态编程问题时发现了这一点。Vn-1给出了一个无括号的表达式，形式为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时）。我需要以下帮助–分析此算法的运行时间。如果有更好的选择。
分析A[i,j]从较短范围到较大范围的元素的计算更加容易。的算法如下：
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)。
A[]
O(n^3)
