我遇到了这个问题。但除了暴力之外，我无法想出任何解决方案。请提出一些有效的算法。给你一个n个数的序列A =（a1，a2，...，an）。只需一步，您可以删除除最左侧和最右侧之外的任何数字。删除号码ai需要花费ai-1 * ai + 1。您的目标是以某种顺序擦除1 <i <n的所有数字ai，以便最小化总成本。给出一个算法来实现你的目标，时间复杂度为O（n ^ 3）。
让DP [a，b]成为问题的解决方案“擦除范围a到b中的所有元素的最小成本，不包括端点a和b本身”。
我假设删除元素的成本是元素之前和之后的条目的乘积。
然后，您可以通过向后思考并考虑“最终条目被擦除的是什么？”来获得O（n ^ 3）算法。如果擦除的最后一个条目位于位置x，则将花费A [a] * A [b]，并且之前我们需要擦除a和x之间的所有条目，以及x和b之间的所有条目。但是，这只是原始问题的另一种情况。
因此，我们可以根据以下重复情况正常构建DP表：
DP[a,b] = A[a]*A[b] + min( DP[a,x] + DP[x,b] for x in range a+1..b-1 )
表中有O（n ^ 2）个条目，对于整体O（n ^ 3）复杂度，它需要O（n）来计算每个条目。