Динамическое программирование: как я могу разбить это в подзадачах?

Question

Я застрял в этой проблеме, и мне нужна помощь:

Учитывая массив arr, на каждом шаге 1, 2 или 5 единиц нужно увеличивать для всех, кромеодин элемент массива (одинаковое количество единиц для всех них).Цель состоит в том, чтобы найти минимальное количество шагов, чтобы все элементы были равны.

Первый пример

arr = [1, 1, 5]

1) [1 (+2), 1 (+2), 5] = [3, 3, 5]
2) [3 (+2), 3 (+2), 5] = [5, 5, 5]

Решение: 2 шага

---

Второй пример

arr = [2, 2, 3, 7]

1) [2 (+1), 2 (+1), 3, 7 (+1)] = [3, 3, 3, 8]
2) [3 (+5), 3 (+5), 3 (+5), 8] = [8, 8, 8, 8]

Решение: 2 шага

---

Я пробовал кое-что, но я действительно застрял.

Я рассматриваю базовый случай, когда все предметы уже равны.В другом случае я пытаюсь найти все возможные решения, увеличивая 1, 2 и 5 для каждого элемента, кроме одного в массиве:

def equal(arr):

    if (allElementsIdentical(arr)):
        return 0

    min = sys.maxsize
    for i in [1, 2, 5]:
        for j in range(len(arr)):

            #Increment all items by "i", except item at index "j"
            newArr = arr.copy()
            for k in range(j):
                newArr[k] += i
            for k in range(j + 1, len(newArr)):
                newArr[k] += i

            movements = 1 + equal(newArr)
            if movements < min:
                min = movements
    return min

Это решение не работает, потому что рекурсия никогда не заканчивается.Например,

[1, 1, 5] -> [1, 2, 6] -> [1, 3, 7] -> [1, 4, 8] -> [1, 5, 9] -> ...

Правильный ли мой первоначальный подход?Как я могу разбить его в подзадачах правильно?Как я могу получить отношение повторения?

(я изучаю Python, поэтому любые комментарии по поводу синтаксиса также приветствуются)

Answer 1

Мы хотим заменить эту проблему на проблему, которая дает тот же ответ, но ее будет легче оценить.

Хитрость в том, чтобы упростить оценку с помощью подхода динамического программирования, состоит в том, чтобы одни и те же результаты появлялись во многих местах. И поэтому мы должны заменить эквивалентные версии этой проблемы на нормализованные.

Для начала ответ не зависит от порядка, в котором находятся элементы массива. Поэтому мы можем заменить наши массивы на массивы, отсортированные от наименьшего к наибольшему. Теперь мы добавляем x ко всему, кроме одного, затем переупорядочиваем в каноническую форму.

Далее ответ не зависит от значения наименьшего элемента. Таким образом, мы можем вычесть это значение из всех записей. Теперь мы добавляем x ко всему, кроме одного, затем переупорядочиваем в каноническую форму, затем вычитаем наименьшее из всего.

Это значительно уменьшает нашу проблему. Достаточно того, что поиск в ширину имеет шанс. Но у нас есть еще один трюк. И дело в том, что не имеет значения, в каком порядке мы применяем операции. И поэтому мы можем применить все наши 5 операций перед нашими 2 операциями перед нашими 1 операциями. С помощью этого трюка мы можем заменить каждый нормализованный узел на (node, last_operation) и начальный last_operation из 5. Причина, по которой это выигрыш, заключается в том, что теперь у нас есть верхняя граница для остальной части поиска A *. Эта граница является текущим числом шагов + сумма ceil(node[i] / last_operation).

И теперь это можно решить с помощью поиска *. Давайте сделаем ваши примеры вручную. Используя обозначения, (total cost, normalized, last_operation, steps).

Пример 1: [1, 1, 5]

Мы нормализуем до [0, 0, 4] и имеем last_operation 5 и стоимость 0+0+1 = 1. Никаких шагов не предпринято. Итак, начнем с:

(1, [0, 0, 4], 5)

Мы убираем это и рассматриваем наши действия. Для операции 5 получаем следующее:

[0, 0, 4] + [5, 5, 0] = [5, 5, 4] => [0, 1, 1] # cost 1 + 0+1+1 = 3
[0, 0, 4] + [5, 0, 5] = [5, 0, 9] => [0, 5, 9] # cost 1 + 0+1+2 = 4
[0, 0, 4] + [0, 5, 5] = [0, 5, 9] => [0, 5, 9] # cost 1 + 0+1+2 = 4 DUP

А для операции 2 получаем:

[0, 0, 4] + [2, 2, 0] = [2, 2, 4] => [0, 0, 2] # cost 1 + 0+0+1 = 2
[0, 0, 4] + [2, 0, 2] = [2, 0, 4] => [0, 2, 4] # cost 1 + 0+1+2 = 4
[0, 0, 4] + [0, 2, 2] = [0, 2, 4] => [0, 2, 4] # cost 1 + 0+1+2 = 4 DUP

А для операции 1 получаем:

[0, 0, 4] + [1, 1, 0] = [1, 1, 4] => [0, 0, 3] # cost 1 + 0+0+3 = 4
[0, 0, 4] + [1, 0, 1] = [1, 0, 4] => [0, 1, 4] # cost 1 + 0+1+5 = 6
[0, 0, 4] + [0, 1, 1] = [0, 1, 4] => [0, 1, 4] # cost 1 + 0+1+5 = 6 DUP

Мы помещаем 7 не дублирований в нашу приоритетную очередь, и лучшее, что получается, выглядит следующим образом:

(total cost, normalized, last_operation, steps)
(         2,    [0,0,2],              2,     1)

Затем мы попробуем выполнить операции 2 и 1 и, разумеется, обнаружим, что одним из результатов будет [0, 0, 0] после 2 шагов.

Answer 2

Мне кажется, что сложение 1, 2 или 5 для всех, кроме одного элемента, гораздо проще представить как вычитание 1, 2 или 5 из всего одного элемента.

[1, 1, 5] -> 5 - 2 -> 3 - 2

[2, 2, 3, 7] -> 3 - 1 -> 7 - 5

Чтобы построить повторение, мы можем использовать гистограмму и считать, что для сдвига любого значения будет стоить его частота в операциях.Так как нам разрешено уменьшать на 1, мы можем легко установить нижнюю границу для самой низкой цели, к которой нам может потребоваться сместить все значения.Поскольку наименьшее значение может быть достигнуто любым другим значением, смещение всех значений до (lowest-5) (как отмечает HackerRank редакционная ), потребует на n больше операций, чем смещение всех элементов вниз к наименьшему, так каксначала мы сдвигаем все элементы к наименьшему, затем применяем (-5) к каждому.

Также в редакционной статье отмечается, что наименьшее количество операций, k, для смещения x к цели 0, может быть найден в O (1) жадным

k = x / 5 + (x % 5) / 2 + (x % 5) % 2

Так как вы попросили скорее попытаться сформировать повторение, в этих обстоятельствах нам осталось бы решить проблему замены монет (монеты[5, 2, 1]) для каждого значения в гистограмме, чтобы достичь цели.Они независимы: не имеет значения, в каком порядке мы применяем coin_change к каждому значению, чтобы найти количество необходимых операций, которые мы затем умножаем на частоту значения.Подсчитывая общее количество операций по всем значениям для достижения каждой цели, мы выбираем наименьшее.