如何从相邻对的序列中找到元素选择的最小成本

Question

给定一个整数数组（至少有两个元素），我需要以成本最低的方式从数组中每对相邻元素中至少选择一个元素。然后，返回成本和选择的元素。
例如，

[50, 30, 40, 60, 10, 30, 10]

我们为 (50, 30) 对和 (30, 40) 选择 30。然后我们为 (40, 60) 对选择 40，对 (60, 10), (10, 30) 选择 10。最后，这对 (30, 10) 为 10。所以我们得到 30 + 40 + 10 + 10 = 90。

另一个例子，

[60, 100, 70]

有两种可能的选择：[60, 70] 或 [100]。但是，最优解是 [100]，总共 100，小于 60 + 70。因此，算法应该选择 100。

我的问题是，我只成功地制作了返回最低成本的代码，而没有保存所使用的元素。

我的Python代码

arr = [50, 30, 40, 60, 10, 30, 10]
min_sum = [0] * len(arr)
min_sum[0] = arr[0]
min_sum[1] = arr[1]

for i in range(2, len(arr)):
    choice1 = min_sum[i-1] + arr[i]
    choice2 = min_sum[i-2] + arr[i]
    min_sum[i] = min(choice1, choice2)

res = min(min_sum[-1], min_sum[-2])
print(res)

Answer 1

如果我理解正确，您可以保存索引而不是元素，然后通过这些索引重新创建所需的输出：

lst = [50, 30, 40, 60, 10, 30, 10]

out = []
for i in range(len(lst) - 1):
    mn = min(i, i + 1, key=lambda k: lst[k])
    if not out or mn != out[-1]:
        out.append(mn)

out = [lst[i] for i in out]
print(out)

打印：

[30, 40, 10, 10]

Answer 2

您还可以查看以下其他方法。我添加了当有一个左侧元素时的情况。在你的代码中，一旦你的列表是 [50, 30, 40, 60, 10, 30, 10,10]，你就会得到相同的总和，但是你有额外的一个元素。在此示例中，您的代码的总和为 90，但它应该是 100。因此，我添加了这部分以避免遗漏。

if l==len(arr)-1: #Check if there is only one element left to check
    res.append(arr[l]) 

最终代码应该是这样的。

arr = [50, 30, 40, 60, 10, 30, 10]


l = 0
r = 1
res = []
while r<len(arr):
    min_value = min(arr[l],arr[r])
    res.append(min_value)
    print(min_value)

    if min_value==arr[r]: 
        l+=2
        if l==len(arr)-1 and r != len(arr)-1: #Check if there is only one element left to check
            res.append(arr[l])
        r+=2
        
    else:
        l+=1
        r+=1
    

print(res,sum(res))

Answer 3

arr = [50, 30, 40, 60, 10, 30, 10]  

my_set: set = set(i if elem[0] <= elem[1] else i + 1 for i, elem in enumerate(zip(arr[:-1], arr[1:])))  

# using lists
my_list: list[int] = [arr[i] for i in my_set]  
print(my_list)  # the values from the initial list
print(sum(my_list))  # sum of values from the initial list

# using dictionaries
my_dict: dict = {i: arr[i] for i in my_set}  
print(list(my_dict.values()))  # the values from the initial list
print(sum(list(my_dict.values())))  # sum of values from the initial list