给定一个有N个顶点和N条边的多边形。每个顶点上都有一个整数(可以是负数),每条边上都有一个操作符(在集合*和+中)。每次从多边形中移除一条边E,将由该边连接的两个顶点(V1,V2)合并成一个新顶点,其值为:V1 op(E) V2。最后一种情况是只剩下两个带有两条边的顶点,结果是两者中的大值。
返回给定多边形所能获得的最大结果值。
对于最后一种情况,我们可能不需要合并两个顶点,因为另一个数字可能是负数,在这种情况下,我们将只返回更大的数字。
我如何解决这个问题:
p[i,j] denotes the maximum value we can obtain by merging nodes from labelled i to j.
p[i,i] = v[i] -- base case
p[i,j] = p[i,k] operator in between p[k+1,j] , for k between i to j-1.
and then p[0,n] will be my answer.
Second point , i will have to start from all the vertices and do the same as above as this will be cyclic n vertices n edges.
The time complexity for this is n^3 *n i.e n^4 .
我能做得比这更好吗?