Python 如何求相邻对序列中元素 Select 的最小代价

当只考虑直到元素i的数组时，将cost(i)称为最优解的成本，此问题有一个简单的递归公式:

cost(i) = min(
    arr[i] + cost(i-1),
    arr[i-1] + cost(i-2),
)

例如，数组[50，30，40，60，10，30，10]的成本是

10 + cost for [50, 30, 40, 60, 10, 30]
30 + cost for [50, 30, 40, 60, 10]

这种复发的基本情况是:

cost(0) = 0
cost(1) = 0
cost(2) = min(arr[0],arr[1])

这种递归关系导致了一个简单的迭代代码:

def cost(a):
    if len(a) <= 1:
        return 0
    elif len(a) == 2:
        return min(a)
    cost_iminus2 = 0
    cost_iminus1 = min(a[:2])
    for i in range(2,len(a)):
        cost_i = min(
            arr[i] + cost_iminus1,
            arr[i-1] + cost_iminus2,
        )
        cost_iminus2, cost_iminus1 = cost_iminus1, cost_i
    return cost_i

您可以轻松地修改此代码，以记住和中使用了哪些元素:

def selection(a):
    if len(a) < 2:
        return 0, []
    elif len(a) == 2:
        return min(a), [min(a)]
    cost_iminus2, selection_iminus2 = 0, []
    cost_iminus1, selection_iminus1 = min(a[:2]), [min(a[:2])]
    for i in range(2,len(a)):
        cost_i = min(
            a[i] + cost_iminus1,
            a[i-1] + cost_iminus2,
        )
        if cost_i == a[i] + cost_iminus1:
            selection_i = [*selection_iminus1, a[i]] # need to copy
        elif cost_i == a[i-1] + cost_iminus2:
            selection_i = selection_iminus2 # no need to copy
            selection_i.append(a[i-1])
        else:
            raise ValueError("unreachable branch")
        cost_iminus2, cost_iminus1 = cost_iminus1, cost_i
        selection_iminus2, selection_iminus1 = selection_iminus1, selection_i
    return cost_i, selection_i

输出:

>>> selection([50, 30, 40, 60, 10, 30, 10])
(90, [30, 40, 10, 10])
>>> selection([60,100,70])
(100, [100])