在这个游戏中获得最高分：选择和删除数组中的元素

Question

给定一个 arr 数组 n 整数，玩家在玩以下游戏时可以达到的最高分数是多少？

选择数组中的索引 0 < i < n-1
给分数加arr[i-1] * arr[i+1]分（初始分数为0）
通过删除元素 i 来缩小数组（forall j >= i: arr[j] = arr[j+1]; then n = n - 1
重复步骤 1-3 直到 n == 2。

执行上述操作直到只有 2 个元素（第一个和最后一个元素，因为您无法删除它们）。

你能得到的最高分是多少？

例子

arr = [1 2 3 4]

选择i=2，得到：2*4=8分，去掉3

剩余：arr = [1 2 4]

选择i=1，得到1*4 = 4分，去掉2分

剩余：arr = [1 4].

总分是 8 + 4 = 12，这是这个例子的最高分。

我认为它与动态规划有关，但我不确定如何解决它。

Answer 1

这个问题有一个类似于Matrix-chain multiplication problem的动态规划方法。您可以在《算法导论》第 3 版（Cormen，第 370 页）一书中找到进一步的解释。

让我们找到最优子结构属性，然后用它从最优解到子问题构造问题的最优解。
表示法：C_i..j，其中i≤j，代表元素C_i，C_i+1,...,C_j.
定义：C_i..j 的移除序列是 i+1,i+2,...,j-1.
的排列如果按该顺序删除 C_i..j 的元素所获得的分数最大，则 C_i..j 的删除序列是最优的在 C_i..j.

的所有可能删除序列中

1.表征最优解的结构
如果问题是非平凡的，即 i + 1 < j，那么任何解决方案都有一个最后删除的元素，其对应的索引是范围内的 k 我 < k < j。这样k把问题拆分成C_i..k和C_k..j。也就是说，对于某个值 k，我们首先删除 C_i..k 和 C_k..j 的非极值元素，然后我们删除元素 k。由于删除 C_i..k 的非极值元素不会影响通过删除 C_k..j 的非极值元素和一个删除 C_k..j 的非极值元素的类似推理也是正确的，我们声明两个子问题都是独立的。然后，对于给定的删除序列，其中 kth-element 在最后，C_i..j 的分数等于 C_{i 的分数之和。 .k}和C_k..j，加上去掉kth-element的分数(C[i] * C[j]).

这个问题的最优子结构如下。假设对于 C_i..j 有一个最优的移除序列 O 结束于 kth-element，那么从 C_{i..k 中移除元素的排序} 也必须是最优的。我们可以用反证法证明：如果 C_i..k 有一个移除序列得分高于从 O 中提取的 C_{i..k[ 移除序列=87=] 那么我们可以为 C_i..j 生成另一个移除序列，其得分高于最佳移除序列（矛盾）。对于 C_i..j 的最佳删除序列中从 C_k..j 中删除的元素的排序也有类似的观察：它必须也是最优的。}

我们可以通过将问题拆分为两个子问题，找到子问题实例的最优解，并将这些最优子问题解组合起来，为问题的非平凡实例构建最优解。

2。递归定义一个最优解的值.

对于这个问题我们的子问题是在C_i..j中获得的最大分数对于1≤i≤j≤N。让S[i,j]是最大值在C_i..j中得到的分数；对于完整问题，评估给定规则时的最高分是 S[1, N].

我们可以递归定义S[i, j]如下：
如果 j ≤ i + 1 则 S[i, j] = 0
如果 i + 1 < j 那么 S[i, j] = max_{i < k < j}{S[i, k] + S[k, j] + C[i] * C[j]}

我们确保搜索正确的拆分位置，因为我们考虑了所有可能的位置，因此我们确信已经检查了最佳位置。

3。计算最优解的值

您可以使用自己喜欢的方法计算 S:
top-down 方法（递归）
bottom-up 方法（迭代）\

我会使用 bottom-up 来计算解决方案，因为在几乎任何编程语言中它都不会超过 5 行。

C++11 中的示例：

for(int l = 2; l <= N; ++l) \ increasing length intervals
    for(int i = 1, j = i + l; j <= N; ++i, ++j)
        for(int k = i + 1; k < j; ++k)
            S[i, j] = max(S[i, j], S[i, k] + S[k, j] + C[i] * C[j])

4。时间复杂度和 Space 复杂度

有 nC2 + n = Θ(n²) 个子问题，每个子问题做一个操作运行时间是 Θ(l) 其中 l 是长度子问题，因此数学为算法产生了 Θ(n³) 的运行时间（很容易发现 O(n³) 部分 :-))。此外，该算法需要 Θ(n²) space 来存储 S table.

在这个游戏中获得最高分：选择和删除数组中的元素

Get highest score in this game: choosing and removing elements in an array

algorithm

dynamic-programming