我正在写一个程序:
例如输入是 5(它可以不仅是 5)个数字,我读取数组中的数据:1, 2, 3, 4, 5
。我可以从这个数组中选择一些元素(不是第一个或最后一个),例如3,然后我删除数组中的这个数字,并将 sum
(最初为 0 )添加乘以 first-to-the-left 和 first-to-the-right 元素(意味着 2 *4
在这种情况下)。结果数组是 1, 2, 4, 5
,然后我一次又一次地这样做,直到元素数等于 2(正是 1 和 5
,因为我们无法删除它们数字)。
例如:(其中 A、B、C、D 是一对数字 1 和 2、2 和 3 等等。)
A B C D
1 2 3 4 5
删除元素的顺序有6种可能的组合(加上左右乘法求和):
A (B (C D))
A ((B C) D)
(A B) (C D)
(A (B C)) D
((A B) C) D
A (B (C D))
目标是找到最小的总和!有两种解决方法,一些聪明的算法或对每个组合使用递归,然后选择最小的一个。任何人都可以告诉我如何编写这样的递归,从哪里开始编写(或者一些聪明的算法)。发送
最佳答案
递归回溯解决方案相当简单(伪代码):
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!))
,因此该算法的速度不够快,无法处理非平凡的数据集。优化递归解决方案的常用方法是 dynamic programming .让我们提出子状态:
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))
,它应该在合理的时间内针对中小型数据集运行。
关于C递归函数寻找最小值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13589351/