Python Гвоздики В дощечку в один ряд вбиты гвоздики.

Question

Гвоздики
В дощечку в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
Входные данные
В первой строке входных данных записано число N — количество гвоздиков (2≤N≤100). В следующей строке заданы N чисел — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
Выходные данные
Выведите единственное число — минимальную суммарную длину всех ниточек.
Примеры
Ввод
Вывод
6
3 4 6 12 13 14
5

dmitry_676 · Accepted Answer

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
d = [0] * n
d[1] = lst[1] - lst[0]
if n > 2:
    d[2] = lst[2] - lst[0]
    for i in range(3, n):
        d[i] = min(d[i - 2], d[i - 1]) + lst[i] - lst[i - 1]
print(d[n - 1])