C递归函数找到最小值

Question

我正在写一个程序:

例如,输入是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))

目标是找到最小的总和!有两种解决方法,一些聪明的算法或每种组合使用递归,然后选择最小的一种.任何人都可以给我一个提示如何编写这样的递归,从哪里开始编写(或者可能是一些聪明的算法).TNX

Answer 1

递归回溯解决方案相当简单(伪代码):

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)),其应该在合理的时间内针对中小型数据集运行.