How to find min cost for element selection from a sequence of adjacent pairs

Question

Given an array of integers (with at least two elements), I need to choose at least one element of each adjacent pair of elements in the array in a way that costs me the least. Then, return the cost and elements chosen.
For example,

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

We choose 30 for the pair (50, 30), and for the pair (30, 40). Then we choose 40 for the pair (40, 60) and 10 for the pairs (60, 10), (10, 30). Lastly, 10 for the pair (30, 10). So we got 30 + 40 + 10 + 10 = 90.

Another example,

[60, 100, 70]

There are two possible selections: [60, 70] or [100]. But, the optimal solution would be [100] for a total of 100, which is less than 60 + 70. So, the algorithm should choose 100.

My issue is that I only succeeded in making a code that returns the lowest cost without saving the elements used.

My Code in 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

Calling cost(i) the cost of the optimal solution when considering the array up to element i included only, there is a simple recurrence formula for this problem:

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

For instance, the cost for array [50, 30, 40, 60, 10, 30, 10] is the minimum of

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

The base cases for this recurrence are:

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

This recurrence relation leads to a simple iterative code:

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

You can easily amend this code to also remember which elements were used in the sum:

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

Output:

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

Answer 2

If I understand you correctly, you can save the indices instead of elements, then recreate the desired output by these indices:

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)

Prints:

[30, 40, 10, 10]

Answer 3

Here is other ways that u can take look. I added case when have one left element. in your code u going to get the same sum once ur list is [50, 30, 40, 60, 10, 30, 10,10] but u have extra one element. In this example your code will have sum as 90 but it should be 100. So, I added this part to avoid missing that.

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

Final code should be like that.

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 4

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