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

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]