3

我正在编写一个程序：

例如输入是 5 （它不仅可以是 5 ）数字，我读取数组中的数据：1, 2, 3, 4, 5。我可以从这个数组中选择一些元素（不是第一个或最后一个），例如 3，然后我在数组中删除这个数字，然后sum（最初是 0）将相乘的第一个到左边与第一个相加相加正确的元素（2*4在这种情况下是指）。结果数组是1, 2, 4, 5，然后我一次又一次地这样做，直到元素数等于 2 （1 and 5正如我们不能删除这些数字一样）。

例如：（其中 A、B、C、D 是成对的数字 1 和 2、2 和 3 等。）

 A B C D
1 2 3 4 5

删除元素的顺序有 6 种可能的组合（并将左右乘法添加到 sum ）：

A (B (C D))
A ((B C) D)
(A B) (C D)
(A (B C)) D
((A B) C) D
A (B (C D))

目标是找到最小的总和！有两种解决方法，一些聪明的算法或对每个组合使用递归，然后选择最小的一个。谁能给我一个提示如何编写这样的递归，从哪里开始编写（或者可能是一些聪明的算法）。肿瘤坏死因子

4

1 回答 1

8

递归回溯解决方案相当简单（伪代码）：

def solve (list): 
    if list.length == 2:
        return 0
    ans = INFINITY
    for each interior element:
        remove element from list
        ans = min(ans, leftelement * rightelement + solve(list))
        place element back in original position in list
    return ans

然而，这个算法不够快，无法处理非平凡的数据集，因为它的运行时间是阶乘的(O(n!))。优化递归解决方案的常用方法是动态规划。让我们提出子状态：

dp[a][b]: minimum cost to reduce array[a .. b] to two elements on the edge
          (array[a] and array[b])

基本情况是dp[i][i + 1], i = {0 .. size - 1)（两个相邻的元素）。由于没有要删除的内部元素，因此此子状态设置为 0。

对于所有其他情况dp[a][b]，b - a >= 2我们可以array[a .. b]通过删除在 之间索引的任何内部元素来进行划分[a + 1, b - 1]。如果我们在元素 i 上划分子数组，则成本为dp[a][i] + dp[i][b] + array[a] * array[b]。我们希望最小化每个子状态的成本，因此我们将对所有可能的划分元素取这些值中的最小值。最后的答案很简单dp[0][size - 1]。

由于存在O(n^2)子状态，每个子状态都需要考虑平均O(n)划分元素，因此总运行时间为三次(O(n ^ 3))，它应该在合理的时间内针对中小型数据集运行。

于 2012-11-27T18:13:52.403 回答